模板题 直接求欧拉函数即可
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a,b,t,k; 4 int euler_phi(int n) 5 { 6 int m = sqrt(n+0.5); 7 int ans = n; 8 for(int i=2;i<=m;i++) 9 { 10 if(n%i==0) 11 { 12 ans=ans/i*(i-1); 13 } 14 while(n%i==0)n/=i; 15 } 16 if(n>1)ans = ans /n*(n-1); 17 return ans; 18 } 19 int main() 20 { 21 while(cin>>a) 22 { 23 cout<<euler_phi(a)<<endl; 24 } 25 return 0; 26 }