欧拉函数
(欧拉函数) $O(sqrt(n))$
时间复杂度
sqrt(n)
C++ 代码
#include <iostream>
using namespace std;
// 欧拉函数
int phi(int 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; // 把所有的2全部干掉了
}
// 还有质因子
if (x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
cout << phi(x) << endl;
}
return 0;
}