ながめも

競技プログラミングについて

トップ > AtCoder Beginner Contest 165 D - Floor Function

AtCoder Beginner Contest 165 D - Floor Function

D - Floor Function

問題概要

\displaystyle f(x) = \left\lfloor\frac{Ax}{B}\right\rfloor- A\left\lfloor\frac{x}{B}\right\rfloorの最大値を求めよ。ただし1\le x \le Nとする。

解説

一般に床関数は以下のように表せる。

\displaystyle \left\lfloor\frac{a}{b}\right\rfloor = \frac{a-a\%b}{b}

よって、

\displaystyle \left\lfloor\frac{Ax}{B}\right\rfloor = \frac{Ax - (Ax)\%B}{B} = \frac{Ax - (A(x\%B))\%B}{B}

\displaystyle A\left\lfloor\frac{x}{B}\right\rfloor = A\frac{x-x\%B}{B} = \frac{Ax-A(x\%B)}{B}

ゆえに、

\displaystyle f(x) = \frac{Ax - (A(x\%B))\%B}{B} - \frac{Ax-A(x\%B)}{B} = \frac{A(x\%B) - (A(x\%B))\%B}{B} = \left\lfloor\frac{A(x\%B)}{B}\right\rfloor

したがって、

f(x)はx = \min(N, B -1)のとき最大になる。