題目：給定
個(gè)正整數(shù)
耕陷，請你求出每個(gè)數(shù)的歐拉函數(shù)仲吏。
歐拉函數(shù)： 中與
互質(zhì)的數(shù)的個(gè)數(shù)被稱為歐拉函數(shù)萎津，記為
。公式如下：
其中是
的質(zhì)因子。
互質(zhì)：兩個(gè)數(shù)的最大公因數(shù)是1经备，即兼雄。
證明：
假設(shè)是
的質(zhì)因子，則在
中
的倍數(shù)有
占业，一共
個(gè)绒怨。同理
和
的倍數(shù)有
個(gè)。如果把這
個(gè)數(shù)去掉谦疾，則
被多去了一次南蹂，需要加回來，但加回來后此時(shí)
被少去了一次念恍，所以需要再去掉一次六剥，故有在
非
的倍數(shù)有：
故若，
是
的質(zhì)因子峰伙，則
非
的倍數(shù)有：
而在 中與
不互質(zhì)的只有其質(zhì)因子的倍數(shù)疗疟，所以與
互質(zhì)的數(shù)的個(gè)數(shù)即為
中非其質(zhì)因子倍數(shù)的個(gè)數(shù)，從而有：
算法實(shí)現(xiàn)：
#include <iostream>
#include <cstring>
#include <algorithm>
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;
}
