AT_abc020_d.[ABC020D] LCM Rush

$2$ 个正整数 $a$、$b$ 的最小公倍数 $LCM(a,\ b)$，是指既是 $a$ 的倍数又是 $b$ 的倍数的所有正整数中最小的一个。

给定两个正整数 $N$、$K$。请计算对于所有 $1$ 到 $N$ 之间的整数 $i$，$LCM(i,\ K)$ 的和，并将结果对 $1,000,000,007$ 取余。

输入以以下格式从标准输入给出。

$N$ $K$

• 第 $1$ 行包含两个用空格分隔的整数 $N$、$K$，满足 $1 \leq N, K \leq 10^9$。

请输出所求的和对 $1,000,000,007$ 取余的结果。

注意不要忘记输出末尾的换行符。

部分分

由于本题作为 AtCoder Beginner Contest 的题目来说非常难，因此本题总分为 $101$ 分，并设置了部分分。

• 有 $5$ 分的测试点满足 $1 \leq N, K \leq 100$。
• 另有 $10$ 分的测试点满足 $1 \leq N \leq 10^4, 1 \leq K \leq 100$。
• 还有 $85$ 分的测试点满足 $1 \leq N \leq 10^9, 1 \leq K \leq 100$。以上共计 $100$ 分。

样例解释 1

$LCM(1,\ 2) + LCM(2,\ 2) + LCM(3,\ 2) + LCM(4,\ 2) = 2 + 2 + 6 + 4 = 14$。

由 ChatGPT 4.1 翻译