ETF - Euler Totient Function
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
//{$APPTYPE CONSOLE}
{$MODE DELPHI}
var
f, t : array[1..1000000] of integer;
i, j, n, st : integer;
begin
f[1] := 1;
for i:=1 to 1000000 do t[i] := i;
for i:=2 to 1000000 do if t[i] = i then
begin
j := i + i;
while j <= 1000000 do
begin
t[j] := i;
j := j + i;
end;
end;
for i:=2 to 1000000 do
begin
n := i;
j := 1;
while n mod t[i]=0 do
begin
n := n div t[i];
j := j * t[i];
end;
f[i] := f[n] * (j - j div t[i]);
end;
read(st);
while st > 0 do
begin
read(n);
writeln(f[n]);
dec(st);
end;
end.