問題概要
正整数 $A, B, N$ が与えられる．$\mathrm{ floor }\left( \frac{ A x } B \right) - A ~ \mathrm{ floor }\left( \frac x B \right)$ の最大値を求めよ
制約
- $1 \leq A \leq 10^6$
- $1 \leq B, N \leq 10^{ 12 }$
解法
簡単のため，以降，$\mathrm{ floor }$ を $f$ と書きます．
まず問題文中の式を眺めてみると，式中の 2 つの項がともに $\frac x B$ （のようなもの）を含んでいることが分かります．$f$ の挙動が簡単になりそうなケースとして，$x$ が $B$ の倍数の場合を考えてみます．この場合は，$Ax, x$ がともに $B$ の倍数となり，$f$ の引数がともに整数となって，
\begin{align*}
f\left( \frac{ Ax } B \right) - A f\left( \frac x B \right) &= \left( \frac{ Ax } B \right) - A \left( \frac x B \right ) \\
&= \left( \frac{ Ax } B \right) - \left( \frac{ Ax } B \right) \\
&= 0
\end{align*}
で，最小値 $0$ をとります（非負の値の切り下げなので負にはならない）．
また，少なくとも $B$ での剰余が $0$ になる度に値 $0$ になるということから，周期性の匂いがします．確かめてみましょう．式中の $x$ を $x + B$ に置き換えて，っと……，
\begin{align*}
f \left( \frac{ A ( x + B ) } B \right) - A f \left( \frac{ ( x + B ) } B \right) &= f \left( \frac{ Ax } B + \frac{ AB } B \right) - A f \left( \frac x B + \frac B B \right) \\
&= f \left( \frac{ Ax } B \right) + f \left( \frac{ AB } B \right) - A f \left( \frac x B \right) + A f \left( \frac B B \right) \\
&= f \left( \frac{ Ax } B \right) + \frac{ AB } B - A f \left( \frac x B \right) + A \frac B B \\
&= f \left( \frac{ Ax } B \right) + A f \left( \frac x B \right)
\end{align*}
こうなって元の式と同じ式が得られるため，周期性があると分かります．$\frac{ AB } B$ や $\frac B B$ は整数なので切り下げ操作で値が変わらないため，バラしたり $f$ を外したりしています．
周期性があることが分かったので，$x$ の範囲としては $0 \leq x < B$ の範囲だけを考えればよいことになります．この範囲では $\frac x B < 1$ であり，$f \left( \frac x B \right) = 0$ となります．よって，
\begin{align*}
f \left( \frac{ Ax } B \right) + A f \left( \frac x B \right) &= f \left( \frac{ Ax } B \right) + 0A \\
&= f \left( \frac{ Ax } B \right)
\end{align*}
です．この値は（考えている範囲では）明らかに単調非減少であるため，（$N$ との大小関係によって）可能な最大の $x$ をとればよいことになります．
そのような $x$ は $\mathrm{ min }( B - 1, N )$ で求まります（$B \leq N$ のとき $B - 1$, そうでないなら $N$ という風になる）．
この計算は定数回の整数演算でできるので，計算量としては $O( 1 )$ 時間になります．
コード (Haskell)
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine main = do [ a, b, n ] <- readIntegers let x = min ( b - 1 ) n print $ ( a * x `div` b ) - a * ( x `div` b )
