前置知识
莫比乌斯函数定义：
对于一个数 \(n=p_1^{q_1} p_2^{q_2} \cdots p_k^{q_k}\)，其中 \(p\) 为素数，那么
\[\mu(n)=\left\{
\begin{array}{ll}
1, & n=1\\
(-1)^k, & \underset{i=1}{\overset{k}{\prod}}q_i = 1\\
0, & otherwise
\end{array}\right.
\]
莫比乌斯反演的一般形式：\([x = 1] = \underset{d|x}{\sum} \mu(d)\)。
积性函数：对于任意互质的正整数 \(a\) 和 \(b\) 有 \(f(ab)=f(a)f(b)\) 的数论函数。
数论函数：定义域为正整数，陪域为复数的函数。
题目大意
给定 \(a,b\)，求 \(\underset{i=a}{\overset{b}{\sum}} \text{lcm}(i,b) \mod 10^9+7\)。
\(1 \le a \le b \le 10^9\)。
思路
看到 \(\text{lcm}\) 想到 \(\gcd\)。
\[\sum_{i=a}^{b} \text{lcm}(i,b)
=\sum_{i=a}^{b} \frac{ib}{\gcd(i,b)}\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =b\sum_{i=a}^{b} \frac{i}{\gcd(i,b)}\\
\]
然后对于分数，一个常用的套路就是枚举因数。
\[=b\sum_{x|b} \sum_{i=a}^{b} \frac{i}{x} [\gcd(i,b)=x]\\
\ \ \ =b\sum_{x|b} \sum_{i=a}^{b} \frac{i}{x} [\gcd(\frac{i}{x},\frac{b}{x})=1]\\
\ =b\sum_{x|b} \sum_{i=\lceil\frac{a}{x}\rceil}^{\frac{b}{x}} i [\gcd(i,\frac{b}{x})=1]\\
\]
然后我们根据莫比乌斯反演，直接将 \([\gcd(i,\frac{b}{x})=1]\) 换掉。
\[=b\sum_{x|b} \sum_{i=\lceil\frac{a}{x}\rceil}^{\frac{b}{x}} i \sum_{y|\gcd(i,\frac{b}{x})} \mu(y)\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =b\sum_{x|b} \sum_{y|\frac{b}{x}} \mu(y) \sum_{i=\lceil\frac{a}{x}\rceil}^{\frac{b}{x}} i [i \mod y =0]\\
\]
然后发现最后面的那一坨其实就是等差数列求和，直接拆开就好。
\[=b\sum_{x|b} \sum_{y|\frac{b}{x}} \mu(y) \frac{y(\frac{b}{xy}+\lceil\frac{a}{xy}\rceil)(\frac{b}{xy}-\lceil\frac{a}{xy}\rceil+1)}{2}\\
\ \ \ \ =\frac{b}{2}\sum_{x|b} \sum_{y|\frac{b}{x}} \mu(y) y(\frac{b}{xy}+\lceil\frac{a}{xy}\rceil)(\frac{b}{xy}-\lceil\frac{a}{xy}\rceil+1)\\
\]
我们调换一下枚举的顺序，先枚举一个 \(y'=xy\)，然后再枚举 \(x'|y'\)。
\[=\frac{b}{2}\sum_{y'|b} (\frac{b}{y'}+\lceil\frac{a}{y'}\rceil)(\frac{b}{y'}-\lceil\frac{a}{y'}\rceil+1) \sum_{x'|y'} \mu(x') x'\\
\]
找出 \(b\) 的因数就可以解决前面的式子，所以现在我们只需要处理 \(\underset{x'|y'}{\sum} \mu(x') x'\)。
由于 \(b\) 的范围是 \(10^9\)，我们不能直接预处理 \(\mu(x)\)，所以需要另寻方法。
我们令 \(f(x) = \underset{d|x}{\sum} \mu(d) d\)。
\[f(a)f(b)
= \sum_{x|a} \mu(x) x \times \sum_{y|b} \mu(y)y\\
\ \ \ \ \ \ \ \ \ = \sum_{x|a} \sum_{y|b} \mu(x)\mu(y)xy\\
= \sum_{d|ab} \mu(d)d\ \ \ \ \ \ \\
= f(ab)\ \ \ \ \ \ \ \ \ \ \ \ \
\]
所以 \(f(x)\) 是积性函数。
而我们又知道对一个质数 \(p\) 和任意正整数 \(k\)，\(f(p^k)=\mu(1)+\mu(p)p+\underset{i=2}{\overset{k}{\sum}}\mu(p^i)p^i=1-p\)。
所以如果 \(n=p_1^{q_1} p_2^{q_2} \cdots p_k^{q_k}\)，其中 \(p\) 为素数，那么 \(f(n)=\underset{i=1}{\overset{k}{\prod}}1-p_k\)。
那么我们就可以在枚举因数 \(d\) 时直接计算 \(f(d)\) 的值了。
实现细节
多测不清空，爆零两行泪。
代码实现
因为 51nod 没有账号，所以先咕到周末
尾声
如果你发现了问题，你可以直接回复这篇题解
如果你有更好的想法，也可以直接回复！