AcWing 874. 筛法求欧拉函数
原题链接
简单
作者:
dino宋佳奇
,
2024-02-21 00:27:05
,
所有人可见
,
阅读 27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int primes[N],cnt;
int phi[N];
bool st[N];
int n;
ll get_eulers(){
ll ans=1;//phi[1]=1 所以要赋初值为1
for(int i=2;i<=n;i++){
if(!st[i]){
primes[++cnt]=i;
phi[i]=i-1;//如果i是质数说明i之前所有数与其互质
}
for(int j=1;primes[j]<=n/i;j++){
st[primes[j]*i]=true; //由欧拉公式 if n==(p1^a1)*...(pn^an)
if(i%primes[j]==0){ // phi(n)== n*(1-1/p1)*...(1-1/pn)
phi[i*primes[j]]=phi[i]*primes[j];//if(i%j==0)->phi(i*pj)==phi(i)*pj
break;
}
phi[primes[j]*i]=phi[i]*(primes[j]-1);//else phi(i*pj)==phi(i)*pj*(1-1/pj)==phi(i)*(pj-1)
}
ans+=phi[i];
}
return ans;
}
int main(){
scanf("%d",&n);
cout<<get_eulers();
}