ABC090-D-RemainderReminder  を初心者目線で解いていく

1. [問題の概要](#問題の概要)
2. [解答の指針](#解答の指針)
   1. [bの範囲を決定する](#bの範囲を決定する)
   2. [各bに対して、条件を満たすaの数を計算する](#各bに対して、条件を満たすaの数を計算する)
   3. [区間の数を計算する](#区間の数を計算する)
   4. [最後の区間の余りを計算する](#最後の区間の余りを計算する)
   5. [各区間で条件を満たすaの数を計算する](#各区間で条件を満たすaの数を計算する)
   6. [Kが0の場合の特別処理](#Kが0の場合の特別処理)
   7. [答えを出力する](#答えを出力する)
3. [問題のC++コード解説](#問題のC++コード解説)
   1. [入力を受け取る](#入力を受け取る)
   2. [全探索の開始](#全探索の開始)
   3. [区間の計算](#区間の計算)
   4. [答えの計算](#答えの計算)
   5. [Kが0の場合の処理](#Kが0の場合の処理)
   6. [答えの出力](#答えの出力)
4. [最終コード](#最終コード)
[追記:Nの割り方について](#追記: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.入力を受け取る
```C++: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.全探索の開始
```C++:D.cpp
for(ll b = K + 1; b <= N; b++) {
```
bの値をK+1からNまで1ずつ増やしながら全探索を行います。bがK以下の場合、余りがK以上になることはないため、bはK+1からスタートします。

#### 3.区間の計算
```C++:D.cpp
ll q = (N + 1) / b;
ll r = (N + 1) % b;
```
qはN以下でbで割り切れる区間の数を表し、rは最後の区間のNまでの余りを表します。

#### 4.答えの計算
```C++:D.cpp
ans += q * max(0ll, b - K) + max(0ll, r - K);
```
各区間で(b-K)個の数があります。そのため、区間の数qとb-Kの積を答えに加えます。また、最後の区間で条件を満たす数も加えます。

#### 5.Kが0の場合の処理
```C++:D.cpp
if(K == 0) ans--;
```
Kが0の場合、余りが0のペアはカウントから除外します。

#### 6.答えの出力
```C++:D.cpp
cout << ans << endl;
```
最後に計算された答えを出力します。


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

```C++: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`をすることで、区間の数と最後の区間の余りを正確に計算できます。

参考文献：
[はまやんさんの記事](https://blog.hamayanhamayan.com/entry/2018/03/12/092310)