ETF - Euler Totient Function
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#include<cstdio>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxn 1000000
using namespace std;
int f[maxn+10];
void etf()
{
int i,j;
fr(i,1,maxn) f[i]=i/(i%2?1:2);
fr(i,3,maxn)
if (f[i]==i)
for (int j=i;j<=maxn;j+=i)
f[j]=f[j]/i*(i-1);
}
int main()
{
etf();
int test,n;
cin >> test;
while (test--) scanf("%d",&n), printf("%d\n",f[n]);
return 0;
}