欧拉函数介绍
欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。
求欧拉函数
void euler(int n)
{
for (int i=1; i<=n; i++)
phi[i]=0;
phi[1]=1;
for (int i=2; i<=n; i++)
{
if (!phi[i])//这代表i是质数
{
for (int j=i; j<=n; j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
}
}
}
}
