题目大意
给定一个正整数n，要求你求出所有小于n的正整数当中与n互质的数的个数
题解
欧拉函数模板题~~~因为n过大~~~所以直接用公式求
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
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);
return ans;
}
int main()
{
int n;
while(cin>>n&&n)
cout<<euler_phi(n)<<endl;
return 0;
}