线性&&单个 欧拉函数

2018-11-08 16:28:03


//线性筛 
const int N=1e5+100;
int v[N],phi[N],prime[N];
void pre(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!v[i]){
            v[i]=i;
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            int t=prime[j];
            if(t*i>n||t>v[i])break;
            v[i*t]=t;
            if(i%t==0)phi[i*t]=phi[i]*t;
            else phi[i*t]=phi[i]*(t-1);
        }
    }
}
//求单个 
int euler(int x){
    int ans=x;
    for(int j=2;j<=sqrt(x);j++){
        if(x%j==0){
            ans=ans/i*(i-1);
            while(x%j==0)x/=j;
        }
    }
    if(x>0)ans=ans/x*(x-1);
    return ans;
}