問題の概要
この問題では、与えられた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.入力を受け取る
int N;
cin >> N;
for(int i=0;i<N-1;i++) cin>>C[i]>>S[i]>>F[i];
NとKをlong long型の変数として標準入力から受け取ります。
2.全探索の開始
for(ll b = K + 1; b <= N; b++) {
bの値をK+1からNまで1ずつ増やしながら全探索を行います。bがK以下の場合、余りがK以上になることはないため、bはK+1からスタートします。
3.区間の計算
ll q = (N + 1) / b;
ll r = (N + 1) % b;
qはN以下でbで割り切れる区間の数を表し、rは最後の区間のNまでの余りを表します。
4.答えの計算
ans += q * max(0ll, b - K) + max(0ll, r - K);
各区間で(b-K)個の数があります。そのため、区間の数qとb-Kの積を答えに加えます。また、最後の区間で条件を満たす数も加えます。
5.Kが0の場合の処理
if(K == 0) ans--;
Kが0の場合、余りが0のペアはカウントから除外します。
6.答えの出力
cout << ans << endl;
最後に計算された答えを出力します。
最終コード
上の議論をまとめたものが以下のコードになります。
#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をすることで、区間の数と最後の区間の余りを正確に計算できます。
参考文献：
はまやんさんの記事