题目链接：https://vjudge.net/problem/POJ-2407

题意：给出n，求0..n-1中与n互质的数的个数。

思路：欧拉函数板子题，先根据唯一分解定理求出n的所有质因数p1,p2,...,pn，然后根据Φ(m)=m*∏(1-1/pi)计算即可。

AC代码：

#include
     
      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;}