Remainder Reminder [AtCoder Regular Contest 091 D]

https://beta.atcoder.jp/contests/arc091/tasks/arc091_b

解法

https://beta.atcoder.jp/contests/arc091/submissions/2185441

なにかしら全探索して解くんだろうとして考えてみる。
bを全探索すると、条件を満たすaが規則的になるので、そうしよう。
bがK以下の場合は剰余がK以上となることはないので、b=[K+1,N]で全探索する。
　
K≦x % bを満たすaの範囲は

• [K,b-1]
• [K+b, 2b-1]
• ...
• [K+(n-1)b, nb-1]

のようになる。
これを繰り返すと、どこかの区間でnb-1がNを越える。
N以下で範囲が全て入る最大のnを計算しよう。
これは
nb-1=N
n = (N+1)/ b
となるので、計算で求めることができる。
小数となる場合は半端な所でNを越えるということに成るので、切り捨てして、前の範囲を指そう。
各範囲でb-K個の数があるので、(b-K)*nが答えに足される。
　
あとは、n+1の範囲の途中でNがあり、一部条件をみたす場合があるので、それを足そう。
L = K + b*n
R = N
その分を足すと答え。

ll N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
 
    if (K == 0) {
        ll ans = N * N;
        cout << ans << endl;
        return;
    }
 
    ll ans = 0;
    rep(b, K + 1, N + 1) {
        ll n = (N + 1) / b;
        ll d = 0;
        
        d += 1LL * (b - K) * n;
        
        ll L = K + b * n;
        ll R = N;
        if (L <= R) d += R - L + 1;
 
        ans += d;
    }
 
    cout << ans << endl;
}