[AtCoder] ABC 165 D – Floor Function

2020年5月3日2020年12月14日

問題

方針

\[ 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;
}