AcWing 873. 欧拉函数
原题链接
简单
作者:
Drifter
,
2021-01-15 21:00:48
,
所有人可见
,
阅读 378
进阶 Day 1
#include <iostream>
#include <algorithm>
using namespace std;
int get_euler(int x)
{
int res = x;
for(int i = 2; i <= x / i; i++)
{
if(x % i == 0)
{
while(x % i == 0) x /= i;
res = res / i * (i - 1);
}
}
if(x > 1) res = res / x * (x - 1); //very very important!!!
return res;
} //get_euler
int main(void)
{
int n;
scanf("%d", &n);
while (n--)
{
int x;
scanf("%d", &x);
int res = get_euler(x);
printf("%d\n", res);
}
return 0;
}