通式： $\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3}) \cdots (1-\frac{1}{p_n})$
若n是质数p的k次幂：$\phi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以$\phi(n)$表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值，这里函数φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质， $\phi(mn)=\phi(m)\phi(n)$
特殊性质：当n为奇数时， $\phi(2n)=\phi(n)$, 证明与上述类似。
若n为质数则 $\phi(n)=n-1$
zky学长上课时留的思考题，关于$n = \sum_{d|n} \phi(d)$的证明：
①当$n$为质数时，显而易见$n= \sum_{d|n} \phi(d)= \phi(1) + \phi(n) = n$
②当$n=p^a$时
\[ \begin{aligned} n & = \sum_{d|n} \phi(d) \\ & = \sum_{i=0}^a \phi(p^i) \\ & = \phi(1) + \phi(p^1) + \phi(p^2) + \cdots + \phi(p^a) \\ & = 1 + p^1-p^0+p^2-p^1+ \cdots +p^a-p^{a-1} \\ = p^a = n \end{aligned} \]
③当$n$为其他情况时，将$n$分解质因数得$n=p_{1}^{a_{1}}p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$，对于每个$p_{i}^{a_{i}}$是互质的，那么由积性函数的性质($n$和$m$互质，则$\phi(nm)=\phi(n)\phi(m)$)和②中的证明可以得出结论，是不是很简单啊
单个欧拉函数求法：
int euler_phi(int n){
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;++i)
if (n%i==0){
ans=ans/i*(i-1);
while (n%i==0)
n/=i;
}
if (n>1) ans=ans/n*(n-1);
}
欧拉筛，参考白书上的：
int phi[maxn];
void phi_table(int n){
for(int i=2;i<=n;++i)
phi[i]=0;
phi[1]=1;
for(int i=2;i<=n;++i)
if (!phi[i])
for(int j=i;j<=n;j+=i){
if (!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
POJ 2478 O(n)内筛法：
#include<cstdio>
using namespace std;
const int N=1000003;
int num=0,prime[N],phi[N];
bool notp[N];
inline void shai(){
phi[1]=1;
for(int i=2;i<N;++i){
if (!notp[i]){
prime[++num]=i;
phi[i]=i-1;
}
for(int j=1;j<=num&&i*prime[j]<N;++j){
notp[i*prime[j]]=1;
if (i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
int main(){
shai();
int x;
long long ans;
scanf("%d\n",&x);
while (x){
ans=0;
for(int i=2;i<=x;++i)
ans+=phi[i];
printf("%I64d\n",ans);
scanf("%d\n",&x);
}
return 0;
}
这样就可以啦