ARC091 D : Remainder Reminder(400)
作成日：2018.03.14
最終更新日：2018.03.14
問題概要
$N$以下の正整数の組$(a,b)$で、$a$を$b$で割った余りが$K$以上であるようなものの数を求めよ。
制約
$1 \leq N \leq 10^5$
$0 \leq K \leq N-1$
考え方
除算を表す式$a=bq+r$$(0 \leq r \lt b)$において$r \geq K$であるものの数を求めれば良い。
$K=0$の時はすべての組が条件を満たし答えは$N^2$であることは明らかであるから、以下では$K \geq 1$であるとする。
また$K \leq r \lt b$であるから、以下では$b$は$K+1$以上であるとして考える。
$a$を$1$から増やしていくと$r$は$1,2,...,b-1,0,1,...$と周期的に変化する。
そこで$b$を固定して考えると、条件を満たす$a$が$b(q+1) \leq N$である$q$ごとに$((b-1)-K+1)$個、$bq \leq N \lt b(q+1)$を満たす$q$においては$max(0,N\%b-K+1)$個あることが分かる。
$b$は$O(N)$種類なので、$b$の値ごとに考えることで十分高速に答えを求めることができる。
ソースコード
マクロ等はこちら
LL N,K;
LL ans;
int main(){
cin >> N >> K;
if(K == 0) return cout << N*N << endl , 0;
repp(b,K+1,N+1){
ans += N/b * (b-K);
ans += max((LL)0,N%b-K+1);
}
cout << ans << endl;
return 0;
}解法まとめ
$K=0$の時は$N^2$が答えである。(6行)
そうでない時、$K+1 \leq b \leq N$を満たす$b$それぞれについて$[N/b](b-K)$と$max(0,N\%b-K+1)$を加えたものが答えである。(7-11行)