欧拉函数 O(n)=n(1-1/P1)(1-1/P2)…(1-1/Pn) ，其中P1…Pn为n的质因子，求出来的结果就是题目所求。
不知道为社么这么写时间超限，下面那种方式写就能过。
#include<iostream>#include<cstdio>#include<iomanip>#include<cstdlib>#include <algorithm>#include<string.h>#include<queue> #include<math.h>#include<set>#define ll long longusing namespace std;int main(){int t;cin >> t ;while(t--){int n,ans;cin >> n;ans=n;for(int i=2;i*i<=n;i++){if(n%i==0) {//原理：o(n)=n*(1-1/p1)+...+（1-1/pn）p1...pn表示为n的质因子.ans=ans/i*(i-1);//先除后乘，避免溢出。while(n%i==0){n/=i;}}}if(n>1)ans=ans/n*(n-1);cout << ans << endl ;}return 0;}
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;typedef long long LL;const LL maxa=1e10+10;LL euler_deall(LL n){LL res=n;for(LL i=2;i*i<=n;i++){if(n%i==0){res=res/i*(i-1);for(;n%i==0;n/=i);}}if(n!=1)res=res/n*(n-1);return res;}int main(){int t;scanf("%d",&t);while(t--){LLn;scanf("%lld",&n);printf("%lld\n",euler_deall(n));} }
如果觉得《互质数的个数（欧拉函数）C/C++》对你有帮助，请点赞、收藏，并留下你的观点哦！
