問題文
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初学者竞赛问题来说非常困难,所以通常是(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