欧拉函数模板
欧拉函数定义f(n)定义为1-n之间与n互素的数 的个数，即f(n)=n*(1-1/p1)...(1-1/pn)
代码如下：
//欧拉函数
int Euler(int n){
int m=sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;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;
}
//欧拉函数打表
int euler[maxn];
void Euler(int n){
for(int i=2;i<=n;i++){
euler[i]=0;
}
euler[1]=1;
for(int i=2;i<=n;i++){
if(!euler[i]){
for(int j=i;j<=n;j+=i){
if(!euler[j]){
euler[j]=j;
}
euler[j]=euler[j]/i*(i-1);
}
}
}
}