D. Remainder Reminder | AtCoder Regular Contest 091

問題
1<=a,b<=N
a mod b >= K
組(a, b)としてありうるものを数えよ
1<=N<=10^5

 

解説
0<=K<b, q>=0
r >= K
a = bq + r
r = a-bq
K<=r<b
K<=a-bq<b
K+bq<=a<b(q+1)
よって1<=b<=Nの範囲でbを総当たりして
更にK+bq<=N の範囲でqを総当たり
これは調和数を考えると実行時間が
O(NlogN)になるやつ
オーバーフローに注意

Submission #2204827 - AtCoder Regular Contest 091

調和数 (発散列) - Wikipedia