对于正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目，记作φ(n).
算法思路
既然求解每个数的欧拉函数，都需要知道他的质因子，而不需要个数
因此，我们只需求出他的质因子，然后根据公式：N*（p1-1）/p1*(p2-1)/p2......即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; int main() { ll i,j; cin>>n; for(i=0;i<n;i++) { ll x; cin>>x; ll ans=x; for(j=2;j<=x/j;j++) { if(x%j==0) { ans=ans*(j-1)/j; while(x%j==0) { x/=j; } } } if(x!=1) ans=ans*(x-1)/x; cout<<ans<<endl; } return 0; }