D - LCM Rush
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
2 つの正整数 a, b の最小公倍数 LCM(a, b) とは、 a の倍数であり、かつ b の倍数でもあるような正整数のうち最小のものをいいます。
2 つの正整数 N, K が与えられます。 1 以上 N 以下のすべての整数 i について LCM(i, K) を足しあわせたものを 1,000,000,007 で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K
- 1 行目に、 2 個の整数 N, K (1 ≦ N, K ≦ 109) がスペース区切りで与えられる。
部分点
この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 (100 点満点) と異なり 101 点満点であり、部分点が設定されている。
- 5 点分のテストケースは 1 ≦ N, K ≦ 100 を満たす。
- 別の 10 点分のテストケースは 1 ≦ N ≦ 104, 1 ≦ K ≦ 100 を満たす。
- さらに別の 85 点分のテストケースは 1 ≦ N ≦ 109, 1 ≦ K ≦ 100 を満たす。以上で合計 100 点となる。
出力
標準出力に、求める和を 1,000,000,007 で割った余りを出力せよ。
末尾の改行を忘れないこと。
入力例1
4 2
出力例1
14
LCM(1, 2) + LCM(2, 2) + LCM(3, 2) + LCM(4, 2) = 2 + 2 + 6 + 4 = 14 となります。
入力例2
10000 100
出力例2
865504986
入力例3
1000000000 90
出力例3
50001213
入力例4
1000000000 999999900
出力例4
231285006