题目问有多少个小于n的正整数与n互质。
这个可以用容斥原理来解HDU4135。事实上这道题就是求欧拉函数$φ(n)$。
$$φ(n)=n(1-1/p_1)(1-1/p_2)\dots(1-1/p_m)\tag{p为n的质因子}$$
这个通项公式可以通过容斥原理的解法来验证。那么利用这个通项就能在$O(\sqrt[]n)$下计算出φ(n)。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int phi(int n){ 5 int res=n; 6 for(int i=2; i*i<=n; ++i){ 7 if(n%i) continue; 8 while(n%i==0) n/=i; 9 res-=res/i; 10 } 11 if(n!=1) res-=res/n; 12 return res; 13 } 14 int main(){ 15 int n; 16 while(~scanf("%d",&n) && n){ 17 printf("%d\n",phi(n)); 18 } 19 return 0; 20 }
原文：http://www.cnblogs.com/WABoss/p/5183429.html