DIV + MOD-Codeforces

問題リンク-DIV + MOD

問題

以下の関数を考えます。

$a$は定数で$x$は$l$以上$r$以下$(l \leqq x \leqq r)$の時$f_a(x)$が最大となる$x$を求めてください。

解法

場合分けをして考えます。

$\left \lfloor \frac{l}{a} \right \rfloor = \left \lfloor \frac{r}{a} \right \rfloor$の場合

$l \leqq x \leqq r$の範囲で$\left \lfloor \frac{x}{a} \right \rfloor$の値は変化しないので$x \mod a$の取りうる最大の値を求めればよいです。その値は$r \mod a$となります。

$\left \lfloor \frac{l}{a} \right \rfloor \neq \left \lfloor \frac{r}{a} \right \rfloor$の場合

$x$を$l$から$r$へと変化させるとき、$\left \lfloor \frac{r}{a} \right \rfloor - 1$から$\left \lfloor \frac{r}{a} \right \rfloor$へと変わる瞬間があります。この変化の直前に$x \mod a = a-1$となり最大値の候補の1つが得られます。
もう1つの候補は$x = r$の時で$\left \lfloor \frac{x}{a} \right \rfloor$が最大となる時なのでこの2つの候補を比較すれば良いです。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int l, r, a;
    cin >> l >> r >> a;

    if(l/a == r/a){
        cout << r/a + r%a << endl;
    }else{
        int ans = max(r/a - 1 + a-1, r/a + r%a);
        cout << ans << endl;
    }
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}