acwing873.欧拉函数

给定 nn 个正整数 aiai，请你求出每个数的欧拉函数。

欧拉函数的定义

1∼N1∼N 中与 NN 互质的数的个数被称为欧拉函数，记为 ϕ(N)ϕ(N)。
若在算数基本定理中，N=pa11pa22…pammN=p1a1p2a2…pmam，则：
ϕ(N)ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pmN×p1−1p1×p2−1p2×…×pm−1pm

输入格式

第一行包含整数 nn。
接下来 nn 行，每行包含一个正整数 aiai。

输出格式

输出共 nn 行，每行输出一个正整数 aiai 的欧拉函数。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例：

3 3 6 8

输出样例：

2 2 4

#include <iostream>
using namespace std;
int n;
//欧拉函数：求n的质数个数s   n = a1^b1 + a2^b2 + ....  
//s = n/(1-1/a1)(1-1/a2)...
int main(){
    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;
}