摘自ACdreamers的博客
先来介绍几个与欧拉函数有关的定理：
定理一：设m与n是互素的正整数，那么
定理二：当n为奇数时，有。
因为2n是偶数，偶数与偶数一定不互素，所以只考虑2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数值。
定理三：设p是素数，a是一个正整数，那么
关于这个定理的证明用到容斥：
由于表示小于与互素数的正整数个数，所以用减去与它不互素的数的个数就行了。
那么小于与不互素数的个数就是p的倍数个数，有个。所以定理得证。
定理四：设为正整数n的素数幂分解，那么
这个定理可以根据定理一和定理三证明，其实用到的就是容斥。如果对容斥熟悉，其实完全就可以直接容斥。
定理五：设n是一个正整数，那么
这个其实可以看莫比乌斯反演就明白了。
定理六：设m是正整数，(a,m)=1，则：是同于方程的解。
定理七：如果n大于2，那么n的欧拉函数值是偶数。
求单个欧拉函数值：
int phi(int n) { int i,rea=n; for(i=2;i*i<=n;i++) { if(n%i==0) { rea=rea-rea/i; while(n%i==0) n/=i; } } if(n>1) rea=rea-rea/n; return rea; }
线性筛代码：
int phi[maxn], p[maxn], pNum; bool f[maxn]; void init() { for(int i = 2; i < maxn; i++) { if(!f[i]) { p[pNum++] = i; phi[i] = i-1; } for(int j = 0; j < pNum && p[j]*i < maxn; j++) { f[p[j]*i] = 1; if(i%p[j] == 0) { phi[p[j]*i] = phi[i]*p[j]; break; } else phi[p[j]*i] = phi[i]*(p[j]-1); } } }
