原题链接：AcWing 873. 欧拉函数
题目：给定
个正整数
，请你求出每个数的欧拉函数。
欧拉函数： 中与
互质的数的个数被称为欧拉函数，记为
。公式如下：
其中是
的质因子。
互质：两个数的最大公因数是1，即。
证明：
假设是
的质因子，则在
中
的倍数有
，一共
个。同理
和
的倍数有
个。如果把这
个数去掉，则
被多去了一次，需要加回来，但加回来后此时
被少去了一次，所以需要再去掉一次，故有在
非
的倍数有：
故若，
是
的质因子，则
非
的倍数有：
而在 中与
不互质的只有其质因子的倍数，所以与
互质的数的个数即为
中非其质因子倍数的个数，从而有：
算法实现：
#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;
}
