今天离散刚学了欧拉函数 哈哈哈哈， 理解就很easy

时间复杂度

$NO(sqrt(n))$

C++ 代码

//x的质因数：p1，p2, p3 .... pk;
//欧拉函数：phi(x) = x * (1-p1) * (1-p2) * (1-p3) * ...... * (1-pk)


#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int num;
        cin >> num;
        long long ans = num;

        for(int i = 2; i <= num/i; i++)
        {
            if(num % i == 0)
            {
                while(num % i == 0)
                    num /= i;
                ans = ans/i * (i-1);
            }
        }

        if(num > 1)
            ans = ans/num * (num - 1); 

        cout << ans << endl;
    }
}