欧拉函数主要是用来算互质数个数的。
公式就是结论：ϕ(N)表示1 N中与N互质的数的个数结论：ϕ(N)表示1 N中与N互质的数的个数
N=p1a1×p2a2×……×p2a2N=p1a1×p2a2×……×p2a2
ϕ(N)=N(1−1p1)(1−1p2)……(1−1pn)ϕ(N)=N(1−1p1)(1−1p2)……(1−1pn)
=∏ni=1piai=∏i=1npiai
求一个数的复杂度：求一个数的复杂度：n√

题目

#include<iostream>
using namespace std;
int n;
int main()
{
   
    cin>>n;
    while(n--)
    {
   
        int x;
        cin>>x;
        long long ans=x;
        for(int i=2;i<=x/i;i++)
        {
   
            if(x%i==0)
            {
   
                while(x%i==0)
                {
   
                    x/=i;
                }
                ans=ans*(i-1)/i;
            }
        }
        if(x>1) ans=ans*(x-1)/x;
        printf("%lld\n",ans);
    }
    return 0;
}