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