[ABC020D] LCM Rush

题意翻译

- 记两个正整数 $a,b$ 的最小公倍数为 $\operatorname{LCM}(a,b)$。给出两个正整数 $N(1\le N\le 10^9)$ 和 $K(1\le K\le 10^9)$。对于所有整数 $i(1\le i\le N)$,累加 $\operatorname{LCM}(i,K)$ 的值,并求出这个值。由于结果可能很大,你只需要输出答案模 $10^9+7$ 的余数。 - 输入仅包含两个整数 $N$ 和 $K$。输出即为题中所求。

题目描述

[problemUrl]: https://atcoder.jp/contests/abc020/tasks/abc020_d $ 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 $ $ ≦ $ $ 10^9 $) がスペース区切りで与えられる。

输出格式


標準出力に、求める和を $ 1,000,000,007 $ で割った余りを出力せよ。 末尾の改行を忘れないこと。

输入输出样例

输入样例 #1

4 2

输出样例 #1

14

输入样例 #2

10000 100

输出样例 #2

865504986

输入样例 #3

1000000000 90

输出样例 #3

50001213

输入样例 #4

1000000000 999999900

输出样例 #4

231285006

说明

### 部分点 この問題は AtCoder Beginner Contest の問題としては非常に難しいため、通常 ($ 100 $ 点満点) と異なり $ 101 $ 点満点であり、部分点が設定されている。 - $ 5 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N, $ $ K $ $ ≦ $ $ 100 $ を満たす。 - 別の $ 10 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 10^4, $ $ 1 $ $ ≦ $ $ K $ $ ≦ $ $ 100 $ を満たす。 - さらに別の $ 85 $ 点分のテストケースは $ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 10^9, $ $ 1 $ $ ≦ $ $ K $ $ ≦ $ $ 100 $ を満たす。以上で合計 $ 100 $ 点となる。 ### Sample Explanation 1 $ LCM(1,\ 2)\ +\ LCM(2,\ 2)\ +\ LCM(3,\ 2)\ +\ LCM(4,\ 2)\ =\ 2\ +\ 2\ +\ 6\ +\ 4\ =\ 14 $ となります。