证明：容斥原理

$结论： ϕ(N)表示 1 ~ N 中与 N互质的数的个数$
$N=p1^{a1}×p2^{a2}×……×p2^{a2}$
$ϕ(N)=N(1−\frac{1}{p_1})(1−\frac{1}{p_2})……(1−\frac{1}{p_n})$
$=\prod_{i=1}^n {p_i}^{a_i}$
$求一个数的复杂度：$$\sqrt{n}$

#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){
                res=res/i*(i-1);   //防止溢出
                while(x%i==0) x/=i;
            }
        }
        if(x>1) res=res/x*(x-1);
        cout<<res<<endl;
    }
    return 0;
}