欧拉函数

//O(lgn)适用于少求
int euler(int n){
    int ret=n;
    for(int i=2; i*i<=n; i++)
        if(n%i==0){
            ret=ret-ret/i;
            do n/=i;
            while(n%i==0);
        }
    if(n>1)ret=ret-ret/n;
    return ret;
}
/////////////////////////////////////////////////
//O(maxn)
const int maxn;
bool vis[maxn];
int phi[maxn],prime[maxn];
void euler_ini(){
    phi[1]=1;
    int primes=0;
    for (int i=2;i<=maxn;i++){
        if(!vis[i]){
            prime[++primes]=i;
            phi[i]=i-1;
            //由函数本身性质推
        }
        for (int j=1;j<=primes&&i*prime[j]<=maxn;j++){
            vis[i*prime[j]]=true;
            if (i%prime[j])//由积性函数性质推
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else{//找规律
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}