AcWing 873. 欧拉函数（欧拉函数总结）

什么是互质？（最大公因子是1）

判断是否互质。（根据最大公因子是1）

什么是欧拉函数？欧拉函数的公式是？（公式由容斥原理推导而来）

举个例子：（如6的欧拉函数是2，因为1~6之中，首尾的1和6都包括，与6互质的元素个数只有1和5两个）

欧拉函数的证明：运用容斥原理。
链接： 欧拉函数-数论-C++(详细)

算法的时间复杂度主要在分解质因数上，而分解质因数的时间复杂度为O(sqrt(a))，但由于有n组数据，所以时间复杂度为O(sqrt(a)*n)。
算出来本题时间复杂度在4e6~5e6之间，是可以接受的。

由欧拉函数的公式我们可以知道关键是分解质因子p，我们不关心质因子的几次幂（很重要）。

套分解质因子的模板和欧拉函数的公式，求出1~n之间与n互质的元素个数。

#include

using namespace std;

int get_eu(int a)
{
    int res = a;//看公式
    for(int i=2;i<=a/i;++i)
    {
        if(a%i==0)//i为a的质因子
        {
            res = res/i*(i-1);//套公式
            while(a%i==0)
            {
                a/=i;
            }
        }
    }
    if(a>1) res = res/a*(a-1);//套公式
    return res;
}

int main()
{
    int n,a;
    cin>>n;
    while(n--)
    {
        cin>>a;
        cout<