题解 P2568 【GCD】
zhou_yk
2018-07-13 13:44:50
$update\ \ \ 2018/11/18$修改了$Letex$，其他没有变
中间我$AFO$了,成功从红名掉到了蓝名
$update\ \ \ \ 2019/7/22$加了很多自己学文化课时的感悟
$update\ \ \ \ 2019/7/24$发现了一个错误，改了一下
---------------------------------------------------------------------------
先推销一波我的博客[这里](https://www.cnblogs.com/zhouykblog/)
---------------------------------------------------------------------------
听说有一句话数论只会$GCD$，所以我翻开了此题，却发现这题并不是这么简单
所以就写篇题解吧~~(废话真多)~~
-------------
先介绍一个东西：欧拉函数
定义： 对于正整数$n$,小于或等于$n$,且与$n$互质的正整数(包括1)的个数，记作$φ(n)$。($φ(1)=1$)
写成数学公式就是$φ(n)=\displaystyle\sum_{i=1}^n1(gcd(i,n)=1)$
那么答案是什么呢？
我们考虑每个质数$p$对答案的贡献,对于每一个质数$p$
$gcd(x,y)=1$等价于$gcd(a*p,b*p)=p$
所以$gcd(x,y)$为$p$的数对个数即为$1<=a,b<= \frac{n}{p}$中互质对$a,b$的个数,其中不妨令$a<=b$
对于每一个$b,a$有$φ(b)$个取值使$a,b$互质，及$gcd(a*p,b*p)=p$
所以此题答案就是$\displaystyle\sum_{i=1}^n φ(i)$
----------
先介绍一些$φ(n)$的性质：
积性函数(常见的有)
$ε(n)=[n==1]\ \ \ \ \ \ \ d(n)=\displaystyle\sum_{d|n}1\ \ \ \ \ \ \ σ(n)=\displaystyle\sum_{d|n}d $
$ μ(n)=[max(c_1,c_2,...c_m)<=1]*(-1)^m$
当然，还有$φ(n)$喽
积性函数的性质：若$gcd(a,b)==1$则$f(a\times b)=f(a)\times f(b)$
$φ(n)$的其他性质
1.若$p$为质数$φ(p)=p-1$
2.若$p|n$且$p^2|n$，则$φ(n)=φ(n/p)\times p$
3.若$p|n$但是不满足$p^2|n$，则$φ(n)=φ(n/p)\times (p-1)$
4.$\displaystyle\sum_{d|n}φ(d)=n$
------------------------------------------------------------------------------------------------
所以，现在问题就转化为了怎样快速求$φ(n)$
可以联想到欧拉筛法，因为可以在$O(n)$的时间内求出所有质数。
若对于$i$，如果已知所有的$1-i$ 的$φ$，枚举$<=i$的质数$p[j]$，可以求得$φ(x\times p[j])$
1.若$p[j]$与$x$互质 $φ(x*p[j])=φ(x)*φ(p[j])$
2.若不互质，设$x=t*p[j]^k$
$φ(x*p[j])=φ(t*p[j]^{k+1})=φ(t)* φ(p[j]^{k+1})$
$=φ(t)* φ(p[j]^k)*p[j]=φ(x)*p[j]$
所以，预处理$φ(i)$的代码：
```cpp
for (int i=2;i<=n;++i){
if (is_prime[i]) phi[i]=i-1,prime[++prime_num]=i;
for (int j=1;j<=prime_num&&prime[j]*i<=n;++j){
is_prime[prime[j]*i]=0;
if (__gcd(prime[j],i)==1) phi[prime[j]*i]=phi[prime[j]]*phi[i];
else phi[prime[j]*i]=prime[j]*phi[i];
if (i%prime[j]==0) break;
}
}
```
做一下前缀和就可以了
最后提醒一句，$10$年$OI$一场空，不开$long\ long$见祖宗
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10000005;
bool is_prime[N];
int n,prime_num,prime[N],phi[N];
long long sum[N];
int main(){
scanf("%d",&n);
memset(is_prime,1,sizeof(is_prime));
is_prime[1]=0;phi[1]=1;
for (int i=2;i<=n;++i){
if (is_prime[i]) phi[i]=i-1,prime[++prime_num]=i;
for (int j=1;j<=prime_num&&prime[j]*i<=n;++j){
is_prime[prime[j]*i]=0;
if (__gcd(prime[j],i)==1) phi[prime[j]*i]=phi[prime[j]]*phi[i];
else phi[prime[j]*i]=prime[j]*phi[i];
if (i%prime[j]==0) break;
}
}
for (int i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i];
long long ans=0;
for (int i=1;i<=prime_num&&prime[i]<=n;++i)
ans+=(sum[n/prime[i]]<<1)-1;
printf("%lld\n",ans);
return 0;
}
```