欧拉函数f(N)为求1-N中与N互质的数
方法：在1-N中依次减去N的质因数的倍数，但不相同质因数之间可能减重复(如2,3和6)，所以要加上这个减重复的，（离散数学中集合那章有这个容斥原理)
欧拉函数公式如下(展开即为上面那个式子(容斥原理）)：

将公式转化为代码即可

(有收藏题解)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        int res=a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                //res=res*(1-1/i);//公式，但需化简
                res=res/i*(i-1);
                while(a%i==0)a/=i;
            }
        }
        if(a>1)res=res/a*(a-1);
        cout<<res<<endl;
    }
    return 0;
}