はまやんはまやんはまやん

hamayanhamayan's blog

Floor Function [AtCoder Beginner Contest 165 D]

https://atcoder.jp/contests/abc165/tasks/abc165_d

解説

https://atcoder.jp/contests/abc165/submissions/12646306

D問題にしては難しい問題に見えるし、計算過程に実数も入ってくるので、とりあえず実験コードを書いてみる。
xを[0,N]に動かして何か発見が無いか探してみる。
すると、計算式の値はmod Bで周期性があるみたいだ。
かつ、x = B-1(mod B)のときに最大値を取る。
なので、最大値の候補は、x=B-1かx=Nのどちらかとなる。
B-1≦Nとなっているかに注意しつつ、どちらも計算して大きい方を答えよう。
floorは切り捨てなので、整数計算で割り算をすることで代用できる。
実数を介すのは危険なので、整数計算で乗り切ろう。

ll A, B, N;
//---------------------------------------------------------------------------------------------------
ll f(ll x) { return (A * x) / B - A * (x / B); }
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> N;

    ll ans = 0;
    chmax(ans, f(N));
    if (B - 1 <= N) chmax(ans, f(B - 1));
    cout << ans << endl;
}