AcWing 873. 欧拉函数
给定n个正整数aiai，请你求出每个数的欧拉函数。

欧拉函数的定义

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

第一行包含整数n。

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

输出格式

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

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109
输入样例：

3
3
6
8
输出样例：

2
2
4

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

int main(){
    int n;
    cin>>n;
    while(n--){
        int x ;
        cin>>x;
        int res = x;
        for(int i = 2;i<=x/i;i++){
            if(x%i==0)//成立，i是x的质因子
            {
                res = res/i*(i-1);
                while(x%i==0) x/=i;
            }
        }
        if(x>1) res = res/x*(x-1);//x本身就是质因子且大于一
        cout<<res<<endl;//输出欧拉函数的值
    }
    return 0;
}