题解 | 【模板】欧拉函数计算Ⅰ ‖ 朴素求值：试除法 #

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;



int work(int x){
    int ans = x;
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0){
            ans = ans / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) ans = ans / x * (x - 1);
    return ans;
}
signed main(){
    HelloWorld;
    
    int q; cin >> q;
    while(q --){
        int x; cin >> x;
        cout << work(x) << endl;
    }
    return 0;
}

ans = ans / i * (i - 1);