思路：

??(1)歐拉函數：輸入n則輸出1~n中與n互質的數的個數。

（2）計算公式：

（3）證明：（容斥原理）對于n個數，先分別摘除所有被pi整除的數，再回補pij,再刪去pijk;相當于n - n/p1 - n/p2.. - n/pk + n /p1p2 + n/p1p3 + ... +n/pk-1pk - p1p2p3 ....;將其利用分配律結合即為歐拉函數計算公式。

（4）實現：對于x，res初始化為x,先進行質因子分解，拿到質因子后,res = res/n*(n - 1);

代碼：

#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;
}