定理1:对正整数n，欧拉函数是小于等于n的数中与n互质的数的数目（1的欧拉函数为1）
求法（容斥）：
,其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）
定理2:
也就一个正整数n的所有因子的欧拉函数之和等于n。
证明：
先来看一个例子(F代替φ)
12 = F(1)+F(2)+F(3)+F(4)+F(6)+F(12)
F(1) = 1 -> 12
F(2) = 1 -> 6
F(3) = 1,2 -> 4,8
F(4) = 1,3 -> 3,9
F(6) = 1,5 -> 2,10
F(12) = 1,5,7,11 -> 1,5,7,11
通过这个例子，可以知道对于任意正整数x(x<=n),
x 可以唯一表示成 x1*x2，其中x1 = gcd(x,n),x2 = x/x1,且x2与n/x1互质。
则通过枚举所有可能的共同因子d（d|n），加和 F(n/d)。可以发现与1，2，...,n是一一对应的。
虽然感觉挺简单，但是还是写个模板吧
n^(0.5)求一次欧拉函数模板
//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和 ll phi(ll x) { ll sum=x; for(ll i=2;i*i<=x;i++) { if(x%i==0) { sum=sum-sum/i; while(x%i==0) x/=i; } } if(x!=1) sum=sum-sum/x; return sum; }
O(nln(n))打表求出1-n所有的欧拉函数
int phi[1001000]; void getphis(int maxn) { phi[1]=1;
phi[2]=1; for(int i=2;i<=maxn;i++) phi[i]=i; for(int i=2;i<=maxn;i+=2) phi[i]/=2; for(int i=3;i<=maxn;i+=2) { if(phi[i]==i)//为素数 { for(int j=i;j<=maxn;j+=i) { phi[j]=phi[j]-phi[j]/i;
} } } }