D - Remainder Reminder AtCoder Regular Contest 091

D - Remainder Reminder
問題概略
N以下の整数a,bで、a % bがK以上になる組み合わせを数え上げ

制約

• $1\le N\le {10}^5$
• $0\le K\le N-1$
• 入力は全て整数である

 解法

２つの組み合わせの数え上げは、片方を固定するのが鉄板。

bを固定すると、0~Nの全てのaに対してのあまりが周期として分かるので、

0,1,2,b-1,0,1,2,b-1,.....余り

類題

>|java|
public static void main(String[] args)
{
N = sc.nextInt();
K = sc.nextInt();
long res = 0;
for (int b = K + 1; b < N + 1; b++)
{
long group = (N + 1) / b;
long rem = (N + 1) - (group * b);
long add = rem - K > 0 ? rem - K : 0;
res += (b - K) * group + add;
if (K == 0) res--;
}
System.out.println(res);

}
||