题解 P2303 【[SDOi2012]Longge的问题】
sun123zxy
2019-09-22 01:08:18
~~洛谷的markdown为啥不支持多行公式啊啊啊~~
想要公式好看点还是去博客看吧 [传送门](https://www.cnblogs.com/sun123zxy/p/luogu2303withmuandphi.html)，里面也多写了一些有关本题的拓展...
---
bux fixed：
修了下无法正常显示的公式
---
题目传送门：[https://www.luogu.org/problem/P2303](https://www.luogu.org/problem/P2303)
>给定一个整数$n$，求
>$$
>\sum_{i=1}^n \gcd(n,i)
>$$
>
蒟蒻随便yy了一下搞出来个$O(\sqrt{n})$的算法 ~~这题数据怎么这么水~~
首先看到gcd我们就下意识的对它反演一波对吧
### 第一步
$$\sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}$$
这里提供两种化法，得到的结果都是这个。
#### 法一
根据欧拉函数和式
$$n = \sum_{d|n} \varphi(d)$$
暴力推导即可
$$\sum_{i=1}^n \gcd(n,i) = \sum_{i=1}^n \sum_{d|\gcd(n,i)} \varphi(d) $$
$$= \sum_{d|n} \sum_{i=1}^{\frac n d} \varphi(d) $$
$$= \sum_{d|n} \varphi(d) \frac n d$$
#### 法二
根据欧拉函数的定义式
$$\varphi(n) = \sum_{i=1}^n [\gcd(n,i) = 1]$$
PS：$\varphi(n)$表示$1$~$n-1$内与$n$互质的数，将和式上界提升到$n$不但不会影响正确性（$\gcd(n,n) = n \neq 1$），而且让$\varphi(1)$不用特判。
易得
$$\sum_{i=1}^n \gcd(n,i) = \sum_{d|n} d \sum_{i=1}^n [\gcd(n,i) = d] $$
$$= \sum_{d|n} d \sum_{i=1}^{\frac n d} [\gcd(\frac n d,i) = 1] $$
$$= \sum_{d|n} d \varphi(\frac n d) $$
$$= \sum_{d|n} \varphi(d) \frac n d $$
这一步还是比较简单的。~~稍有基础的同学大概都会吧~~
### 第二步
令
$$g(n) = \sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}$$
我们希望求$g$的在$n$的函数值。容易发现右式是狄利克雷卷积$\varphi * Id$，也就是说$g$也是积性函数。所以考虑质因数分解$n$，最后用积性累乘出来
即
$$g(n) = g({p_1}^{c_1}) g({p_2}^{c_2}) ... g({p_n}^{c_n})$$
则只需求$g(p^c)$（这里省略下标）
$p^c$的因数分别为$1$，$p$，$p^2$，...，$ p^c$
所以有
$$g(p^c) = \sum_{i=0}^{c} \varphi(p^i) \frac{p^c}{p^i} $$
$$= \sum_{i=0}^{c} \varphi(p^i) p^{c-i}$$
#### 求$\varphi(p^c)$
考虑先弄出上式中$\varphi(p^i)$的封闭形式，再带回原式看看
根据欧拉函数通式
$$\varphi(n) = n \prod_{i=1}^k (1 - \frac 1 {p_i})$$
（这个$\pi$指的是分解质因数）
易得
$$\varphi(p^c) = p^c (1 - p) $$
$$= p^c - p^{c-1}$$
注意这个式子需要在$c=0$时特判，因为$\varphi(1) = 1$（$1$可以视作分解不出任何质因数）
#### 求$g(p^c)$
得到了$\varphi(p^c)$，带回之前未推完的$g(p^c)$的式子，得
$$g(p^c) = \sum_{i=0}^{c} \varphi(p^i) p^{c-i} $$
$$= p^c + \sum_{i=1}^{c} (p^i - p^{i-1}) p^{c-i} $$
$$= p^c + \sum_{i=1}^{c} (p^c - p^{c-1}) $$
$$= p^c + c (p^c - p^{c-1}) $$
$$= (c+1)p^c - c \ p^{c-1}$$
（中途对$i=0$进行了特殊讨论）（该式同样不适用于$c=0$的情况）
然后积性合并起来就完了
冷静分析一波时间复杂度。质因数分解消耗$O(\sqrt n)$的时间复杂度，分解出不超过$O(log_2 n)$个$p^c$，每个$g(p^c)$的计算是$O(1)$的。所以总时间复杂度为$O(\sqrt n)$
### 代码
非常简单的代码
```c++
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
ll p[1005],c[1005],g[1005];ll kN;
void Div(ll n){
kN=0;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
kN++;p[kN]=i;
g[kN]=1;
ll e=0;while(n%i==0) e++,n/=i,g[kN]*=i;
c[kN]=e;
}
}
if(n!=1) kN++,p[kN]=n,c[kN]=1,g[kN]=n;
}
ll N;
int main(){
cin>>N;
Div(N);
ll pdt=1;
for(int i=1;i<=kN;i++) pdt=pdt*((c[i]+1)*g[i]-c[i]*g[i]/p[i]);
cout<<pdt;
return 0;
}
```
~~这式子长得跟[小粉兔菊苣的题解](https://www.luogu.org/blog/PinkRabbit/solution-p2303)很像？~~