問題の概要
解答の指針
問題のC++コード解説
最終コード
 追記:Nの割り方について

問題の概要

この問題では、与えられたNとKに対して、aをbで割った余りがK以上となるような正の整数のペア(a, b)の組み合わせの数を求めます。

解答の指針

もちろんです。この問題を解くためには、各bに対して、条件を満たすaの数を計算し、その合計を求めます。以下に、より詳細かつ丁寧に解答の指針を説明します。

1. bの範囲を決定する

bの値がK以下の場合、aをbで割った余りがK以上になることはありません。したがって、bの範囲は[K+1, N]となります。bの値をこの範囲で1ずつ増やしながら、各bに対して条件を満たすaの数を計算します。

2. 各bに対して、条件を満たすaの数を計算する

bの値が決まったら、次に、そのbに対して条件を満たすaの数を計算します。これは、[K, b-1]、[K+b, 2b-1]、[K+2b, 3b-1]、...といった区間でaの値が存在します。ただし、最後の区間はNを超えないように注意が必要です。

3. 区間の数を計算する

[K, b-1]、[K+b, 2b-1]、...といった区間の数は、((N + 1) / b)で計算できます。これは、N以下でbで割り切れる区間の数を表します。

4. 最後の区間の余りを計算する

最後の区間で、Nまでの余りは((N + 1) % b)で計算できます。これは、最後の区間でNを超えない最大のaの値を表します。

5. 各区間で条件を満たすaの数を計算する

各区間で条件を満たすaの数は、b-Kです。ただし、最後の区間では、余りの値からKを引いた値となります。これらの値を合計し、答えとします。

6. Kが0の場合の特別処理

Kが0の場合、余りが0のペアは条件を満たさないため、除外します。これは、各bに対して1回ずつ行います。

7. 答えを出力する

最後に、計算された答えを出力します。

このように、bの範囲を正しく設定し、各bに対して条件を満たすaの数を計算し、その合計を求めることで、この問題を解くことができます。

問題のC++コード解説

1.入力を受け取る

D.cpp

int N;
cin >> N;
for(int i=0;i<N-1;i++) cin>>C[i]>>S[i]>>F[i];

NとKをlong long型の変数として標準入力から受け取ります。

2.全探索の開始

D.cpp

for(ll b = K + 1; b <= N; b++) {

bの値をK+1からNまで1ずつ増やしながら全探索を行います。bがK以下の場合、余りがK以上になることはないため、bはK+1からスタートします。

3.区間の計算

D.cpp

ll q = (N + 1) / b;
ll r = (N + 1) % b;

qはN以下でbで割り切れる区間の数を表し、rは最後の区間のNまでの余りを表します。

4.答えの計算

D.cpp

ans += q * max(0ll, b - K) + max(0ll, r - K);

各区間で(b-K)個の数があります。そのため、区間の数qとb-Kの積を答えに加えます。また、最後の区間で条件を満たす数も加えます。

5.Kが0の場合の処理

D.cpp

if(K == 0) ans--;

Kが0の場合、余りが0のペアはカウントから除外します。

6.答えの出力

D.cpp

cout << ans << endl;

最後に計算された答えを出力します。

最終コード

上の議論をまとめたものが以下のコードになります。

D.cpp

#include <iostream>
using namespace std;
typedef long long int ll;

int main() {
    ll N, K;
    cin >> N >> K;
    
    ll ans = 0;
    for(ll b = K + 1; b <= N; b++) {
        ll q = (N + 1) / b;
        ll r = (N + 1) % b;
        ans += q * max(0ll, b - K) + max(0ll, r - K);
        if(K == 0) ans--; // Kが0の場合、余りが0のペアは除外する
    }
    
    cout << ans << endl;
    return 0;
}

あとがき

bの範囲を正しく設定するところと、各ｂ(割る数)に対してaの範囲が,k<=a%bから簡単に求まるという点を意識するのが難しいと思います。

追記:Nの割り方について

n + 1をする理由は、区間の数を正確に計算するためです。具体的には、q = (N + 1) / bとr = (N + 1) % bで、qはN以下でbで割り切れる区間の数を表し、rは最後の区間のNまでの余りを表します。

区間の数の計算

N / bでは、Nをbで割ったときの商、すなわちbで割り切れる区間の数を得ますが、これだけでは最後の区間が正確にカウントされません。例えば、N = 10、b = 4の場合、N / bは2になりますが、実際には[1-4]、[5-8]、[9-10]の3つの区間が存在します。これを正確にカウントするために、N + 1を用います。q = (N + 1) / bでq = 3となり、3つの区間が正確にカウントされます。

余りの計算

同様に、r = (N + 1) % bでは、最後の区間のNまでの余りを正確に計算します。N % bだけでは、最後の区間がbで割り切れる場合に余りが0となり、最後の区間が正確に表現されません。N + 1を用いることで、最後の区間も正確に表現できます。

例えば、N = 10、b = 4の場合、r = (N + 1) % bでr = 3となり、最後の区間[9-10]の余りが正確に計算されます。

このように、n + 1をすることで、区間の数と最後の区間の余りを正確に計算できます。

参考文献：
はまやんさんの記事