标签：1227 frac gcd 公倍数 题解 sum varphi mu text

题目大意

\[A(n)=\frac{1}{n} \sum_{i=1}^{n} \text{lcm}(n,i)\\ F(a,b)=\sum_{i=a}^{b} A(i)\\ \]

给定 \(a,b\)，求 \(F(a,b) \mod 10^9+7\)。

\(1 \le a \le b \le 10^9\)。

思路

首先我们可以想到，如果我们定义 \(B(n)=\underset{i=1}{\overset{n}{\sum}} A(i)\)，那么 \(F(a,b)=B(b)-B(a-1)\)。

然后我们开始逐层推式子。

\[A(n)=\frac{1}{n} \sum_{i=1}^{n} \text{lcm}(n,i)\\ \ \ \ \ \ \ \ \ \ =\frac{1}{n} \sum_{i=1}^{n} \frac{n \times i}{\gcd(n,i)}\\ \ \ \ \ =\sum_{i=1}^{n} \frac{i}{\gcd(n,i)} \]

然后代入 \(B(n)\) 中，根据套路枚举因数，将分母上的 \(\gcd\) 拿出来：

\[B(n)=\sum_{i=1}^{n} A(i)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ =\sum_{i=1}^{n} \sum_{j=1}^{i} \frac{j}{\gcd(i,j)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ =\sum_{i=1}^{n} \sum_{d|i} \sum_{j=1}^{i} \frac{j}{d}[\gcd(i,j)=d]\\ \ \ \ \ \ =\sum_{i=1}^{n} \sum_{d|i} \sum_{j=1}^{i} \frac{j}{d}[\gcd(\frac{i}{d},\frac{j}{d})=1]\\ \ =\sum_{i=1}^{n} \sum_{d|i} \sum_{j=1}^{\frac{i}{d}} j[\gcd(\frac{i}{d},j)=1]\\ \ \ \ \ \ \ \ \ =\sum_{d=1}^{n} \sum_{i=1}^{n} [d|i]\sum_{j=1}^{\frac{i}{d}} j[\gcd(\frac{i}{d},j)=1]\\ =\sum_{d=1}^{n} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{i} j[\gcd(i,j)=1]\\ \]

然后我们再用莫比乌斯反演把 \(\gcd\) 打开：

\[\sum_{j=1}^{i} j[\gcd(i,j)=1]=\sum_{j=1}^{i} j \sum_{x|\gcd(i,j)} \mu(x)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{x|i} \mu(x) \sum_{j=1}^{i} j[j \mod x = 0]\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{x|i} \mu(x) \sum_{j=1}^{\frac{i}{x}} xj\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{x|i} \mu(x) \frac{1}{2}x(1+\frac{i}{x})\frac{i}{x}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{i}{2} \sum_{x|i} \mu(x) (1+\frac{i}{x})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{i}{2} (\sum_{x|i} \mu(x) + \sum_{x|i} \frac{i}{x}\mu(x))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{i}{2} ([i=1]+ \varphi(i))\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{1}{2} ([i=1]+i\varphi(i)) \]

然后我们把这一坨放回原来的式子：

\[B(n)=\sum_{d=1}^{n} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{i} j[\gcd(i,j)=1]\\ \ \ \ \ \ =\frac{1}{2} \sum_{d=1}^{n} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} [i=1]+i\varphi(i)\\ =\frac{n}{2} + \frac{1}{2} \sum_{d=1}^{n} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} i\varphi(i)\\ \]

然后我们设 \(f(i)=i\varphi(i)\)，我们可以简单地推导出 \(f\) 是一个积性函数。

对于互质的两个数 \(a,b\)，\(f(a)f(b)=ab\varphi(a)\varphi(b)\)。

因为 \(\varphi(n)\) 是积性函数，所以 \(\varphi(a)\varphi(b)=\varphi(ab)\)。

所以 \(f(a)f(b)=ab\varphi(ab)=f(ab)\)。

后面是一个整除分块，所以现在我们需要求的实际上是积性函数 \(f(n)\) 的前缀和，可以想到使用杜教筛：

\[(\text{Id}*f)(i)=\sum_{d|i}f(d) \times \text{Id}(\frac{i}{d})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{d|i}d\varphi(d) \times \frac{i}{d}\\ \ \ \ \ =i\sum_{d|i}\varphi(d)\\ =i^2\ \ \ \ \ \ \ \ \]

代入杜教筛公式中，得到：

\[\text{Id}(1)S(n)=\sum_{i=1}^{n} (\text{Id}*f)(i) - \sum_{i=2}^{n} \text{Id}(i)S(\lfloor\frac{n}{i}\rfloor)\\ S(n)=\sum_{i=1}^{n} i^2 - \sum_{i=2}^{n}iS(\lfloor\frac{n}{i}\rfloor) \]

这样我们就求得了 \(S(n)\)。

最后我们利用推出来的公式求解 \(B(n)\) 就好了。

代码实现

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！

标签：1227,frac,gcd,公倍数,题解,sum,varphi,mu,text
From： https://www.cnblogs.com/zsc985246/p/17392004.html