AcWing 873. 欧拉函数
原题链接
简单
作者:
Snrise
,
2024-04-05 17:01:17
,
所有人可见
,
阅读 1
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
int n;
signed main(void)
{
std::ios::sync_with_stdio(false);
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;
}