[AtCoder] ABC 165 D – Floor Function

問題

方針

\[ f(x) = \left \lfloor \dfrac{Ax}{B} \right \rfloor – A\left \lfloor \dfrac{x}{B} \right \rfloor\]

\( 0 \leq x \leq N \) の最大値を求めます。整数 \( k, r \) を用いて、\( x \) を次のように表します。

\[ x = kB + r \ (0\leq r \leq B – 1) \]

このとき、

\begin{eqnarray}
f(kB + r) &=& \left \lfloor Ak + \dfrac{Ar}{B} \right \rfloor – A\left \lfloor k + \dfrac{r}{B} \right \rfloor\\
&=& \left \lfloor \dfrac{Ar}{B} \right \rfloor
\end{eqnarray}

となるので、\( r = \min(B – 1, N) \) のときが最大となります。

コード