[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) \) のときが最大となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll A, B, N; cin >> A >> B >> N; cout << (A * min(B - 1, N)) / B << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません