[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 $ となります。