AtCoder Beginner Contest 020

D - LCM Rush


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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

Submit提出する