定理：
(以下p均为质数)
1. φ(p)=p-1
3. 如果 i mod p ≠ 0 那么 φ(i*p)=φ(i)*φ(p)
2. 如果 i mod p = 0 那么 φ(i*p)=φ(i)*p
证明（其实只要知道结论就好了，证明可以跳过）：
1. 因为$p$是质数，所以$1$ 到 $p$的所有数除了$p$其他均与$p$互质
2. 因为 $i mod p ≠ 0$ 且 $p$为质数，那么 $i$ 与 $p$ 一定互质，由欧拉函数的积性可得 $φ(i*p)=φ(i)*φ(p)$
3. 设$b=gcd(i,p)$
因为$p,i$不互质，所以 $p=k_1b,i=k_2b$
因为 $p+i = (k_1+k_2)b$ ，所以$p+i$ 与 $i$ 不互质，所以对于任意一个 $i$ ，只要 $p$ 与 $i$ 不互质
那么 $p+i$ 与 $i$ 不互质，又因为$p$ 与 $i$ 不互质，所以 $p+i$ 与 $p$ 不互质（$p+i$ 与 $p$ 有公因子 $b$）
所以在 $p+1$ 到 $p+p$ 的闭区间里与 $p$ 不互质的数也有 $i - φ(p)$ 个，
同理$2p+1$ 到 $2p+p$也有 $i - φ(p)$ 个....
所以$1$ 到 $i*p$ 的区间中有 $i*p - i*φ(p)$ 个数与 $p$ 不互质（即与$p$互质的数有 $i*φ(p)$个）
反过来，如果一个数 $i (i<p)$ 与 $p$ 互质，那么 $p+i$ 也与 $p$ 互质
假设 $p+i$ 与 $p$ 不互质
那么设 $b=gcd(p+i,p)，p+i=k_1b,p=k_2b$，那么 $i = p+i-p=k_1b-k_2b=(k_1-k_2)b$ 与 $i,p$ 互质的条件矛盾（有公因子b）
证明完毕。
有了这些条件，我们在用欧拉筛筛质数时就可以一起求出所有数的欧拉函数值了
实现看代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=1e5+7; int n; int pri[N],cnt,phi[N]//phi存欧拉函数值，其他的就是线性筛的东西了; bool not_pri[N]; void get_phi() { scanf("%d",&n); not_pri[1]=phi[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[i]) { pri[++cnt]=i; phi[i]=i-1; }//如果i是质数,phi[i]=i-1 1. for(int j=1;j<=cnt;j++) { int g=i*pri[j]; if(g>n) break; not_pri[g]=1; if(!(i%pri[j])) { phi[g]=phi[i]*pri[j]; break; }//如果i mod p == 0 ，phi[i*p]=phi[i]*p 3. phi[g]=phi[i]*phi[pri[j]];//如果 i mod p !=0，phi[i*p]=phi[i]*phi[p] 2. } } }