题目链接：https://vjudge.net/problem/POJ-2407
题意：给出n，求0..n-1中与n互质的数的个数。
思路：欧拉函数板子题，先根据唯一分解定理求出n的所有质因数p1,p2,...,pn，然后根据Φ(m)=m*∏(1-1/pi)计算即可。
AC代码：
#include<cstdio> using namespace std; int n,ans; int main(){ while(scanf("%d",&n),n){ ans=n; for(int i=2;i*i<=n;++i){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n!=1) ans=ans/n*(n-1); printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10824683.html