欧拉函数（入门）
欧拉函数φ（n）公式法
欧拉函数φ（n）表示：从1~n中与n互质数的个数
若对n进行质因数分解：
则欧拉函数公式：%3Dn*(1-%5Cfrac%7B1%7D%7BP_%7B1%7D%7D)(1-%5Cfrac%7B1%7D%7BP_%7B2%7D%7D)...(1-%5Cfrac%7B1%7D%7BP_%7Bk%7D%7D))
理解Φ（n）=大小*（1-p1所占比重）*（1-p2所占比重）...
在充分混合的情况下，与所有pi都相异的比重=与p1相异的比重*与p2相异的比重*...
与pi相异的数的分布都是每pi个pi-1个，并且n是可以被
整除，所以该式子一定能准确算出
时间复杂度：可知求一个数的φ（n）的瓶颈是分解质因数，为ln（n）
欧拉函数证明：（容斥定理）
1.从1~n中去掉p1、p2....pk的所有倍数
2.加上pi*pj的倍数
3.减掉pi*pj*pk的倍数
......
可以看下1/p1的系数：两边都是-n
phi=a;
for(int i=2;i<=a/i;i++){
if(a%i==0){
phi=phi/i*(i-1);
while(a%i==0) a/=i;
}
}
if(a>1) phi=phi/a*(a-1); 求1~n中的φ（n）筛法
的
当i为质数时 φ（i）=i-1
当i%pj==0，即i是pj的倍数时：φ（i）=i*(1-1/p1)..(1-1/pj)..，φ（i）中已经包含了pj，所以φ（i*pj）=pj*i*(1-1/p1)*...(1-1/pk)=pj*φ（i）
当i%pj！=0，即i倍数pj的倍数时：φ（pj）=pj-1，φ（i*pj）=（pj-1）*φ（i）
phi[1]=1;//先对1求欧拉函数
for(int i=2;i<=n;i++){
if(!st[i]) prime[cnt++]=i, phi[i]=i-1;
for(int j=0;prime[j]<=n/i;j++){
st[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=prime[j]*phi[i]; break;
}else{
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
} 
