题解 P2568 【GCD】

· · 题解

中间我$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)

​ 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)的代码：

    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见祖宗

#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;
}