題目:給定
個(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;
}