873欧拉函数

根据公式，只需分解质因数然后带入计算

细节： phi = phi / i * (i - 1); 计算分数$\frac{i-1}{i}$时先除以 $i$ 再乘上 $i-1$

#include <iostream>
using namespace std;

int n, a, phi;

int main(){
    cin >> n;
    while (n --){
        cin >> a; phi = a;
        for (int i = 2; i <= a / i; i ++){
            if (a % i == 0){
                phi = phi / i * (i - 1);
                while (a % i == 0) a /= i;
            }
        }
        if (a > 1) phi = phi / a * (a - 1);
        cout << phi << endl;
    }
    return 0;
}