AcWing 873. 欧拉函数
原题链接
简单
作者:
Daisy_80
,
2021-08-27 15:20:39
,
所有人可见
,
阅读 128
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int FJ(int x)
{
int front=0;
for(int i=2;i<=x/i;i++)
{
if(x%i==0)
{
a[front++]=i;
while(x%i==0) x/=i;
}
}
if(x!=1) a[front++]=x;
return front;
}
void OL(int x)
{
int Size=FJ(x);
int sum=x;
for(int i=0;i<Size;i++)
{
sum=sum/a[i]*(a[i]-1);
}
printf("%d\n",sum);
}
int main()
{
cin>>n;
while (n -- )
{
int x;cin>>x;
OL(x);
}
return 0;
}