[AtCoder] ABC 090 D – Remainder Reminder

2020年7月22日2020年12月14日

問題

方針

\( K = 0 \) のとき

このとき、\( N \) 以下の全ての正の整数の組 \( (a, b)\) が条件を満たすので、\( N^2 \) が答えとなります。

\( K \neq 0 \) のとき

任意の整数 \( x \) に対して、\( 0 \leq x \bmod b \leq b – 1 \) が成り立つので、\( b \) の値の範囲は、

\[ K + 1 \leq b \leq N\]

となります。ここで、\( a = 0 \) を認めて考えます。実際に \( a \bmod b \) を計算すると以下のようになります。

\begin{array}{c|ccc}
\hline
a & 0 & 1 & 2& \cdots & b – 1 & b & 1 & 2 & \cdots\\
\hline
a \bmod b & 0 & 1 & 2 & \cdots & b – 1 & 0 & 1 & 2 & \cdots\\
\hline
\end{array}

整数 \( n \) を用いて、区間 \( [nb, (n+1)b – 1]\) に対応して \( 0 \leq a \bmod b \leq b – 1 \) となっていることが分かります。ここで、\( N \) 以下を満たす区間の数 \( m \) は、

\[m= \dfrac{N+1}{b} \]

となります。ある区間に \( K \leq a \bmod b \) となる \( a \) の数は、\( b – K \) となるので、全体で \( m(b – K) \) となります。次に、\( m + 1 \) 個目の区間を考えます。この区間は、\( N \) 以下の値も含まれることがあるので、その分を考慮します。\( m + 1 \) 個目区間の最初の値は、\( mb \) となるので、

\[ \max(0, N – (mb + K) + 1)\]

が条件を満たす \( a \) の個数となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll N, K;
    cin >> N >> K;
    if (K == 0) {
        cout << N * N << "\n";
        return 0; 
    }
    ll ans = 0;
    for (int b = K + 1; b <= N; b++) {
        int n = (N + 1) / b;
        ans += n * (b - K) + max(0ll, N - ( n * b + K) + 1);
    }
    cout << ans << "\n";
    return 0;
}