欧拉函数
定义：欧拉函数phi(n)，表示小于或等于n的数中与n互质的数的数目。
欧拉函数的性质：
1. phi(1)=1
2. 若n是素数p的k次幂：phi(n)=p^k-p^(k-1)=(p-1)p^(k-1)
3. 若m,n互质，phi(mn)=phi(m)*phi(n)
欧拉函数的递推式：
令p为n的最小质因数
若p^2|n，则phi(n)=phi(n/p)*p
否则，phi(n)=phi(n/p)*(p-1)
欧拉函数预处理
欧拉函数单个
欧拉函数
原文：http://blog.csdn.net/whai362/article/details/43907907
