AtCoder Beginner Contest 165 D - Floor Function 解説

感想

Cが解けなさすぎて焦っていたのでDを先に見た。
C++の実装例が最後に載っています。

問題

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

思考過程

Nが10の12乗くらいあるので、全探索では到底間に合わない。
floor(Ax/B)とA * floor(x/B)はほとんど同じ値になる。違いは、Bで割ったあまりの分だけ。
詳しく述べると、x = Bk + yと表すことができたとする。その場合、
floor(Ax/B) = Ak + floor(Ay/B)
A * floor(x/B) = Ak
となる。よって、yの部分によってのみ答えが求まり、その答えはyの値が大きければ大きいほどよい、ということがわかる。
よって、そのようなyを求めて、答えを計算する。
具体的には、
NがB以上の場合、yとしてB-1を用いると余りが最大になる。
NがBよりも小さい場合、yとしてNを用いると余りが最大になる。

実装

void solve(){
    cin >> a >> b >> n;
    ll k;
    if(n >= b){
        k = b - 1;
    }else{
        k = n;
    }
    ll ans = k * a / b;
    cout << ans << endl;
    return;
}