欧拉函数模板
模板1:直接求n的phi值
int euler_phi(int n){
int ans=n;
for(int i=2;i*i<=n;i++) if (n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if (n>1) ans=ans/n*(n-1);
return ans;
}
模板2:打欧拉函数表
#define Max 1000009
int euler[Max];
void Init(){
//1的欧拉函数值是1
euler[1]=1;
for(int i=2;i<Max;i++)
euler[i]=i;
for(int i=2;i<Max;i++)
if(euler[i]==i)
for(int j=i;j<Max;j+=i)
euler[j]=euler[j]/i*(i-1);
}