← 返回题目列表

AtCoder · abc020_d

D. LCM 抢购

中文机器翻译题面 查看原题

問題文

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