ETF - Euler Totient Function

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/etf


Trong số học, hàm Ơ-le của một số nguyên dương n được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n.

Cho số nguyên dương n (1 <= n <= 10^6). Tính giá trị của hàm Ơ-le .

Input

Dòng đầu chứa số nguyên T là số test (T <= 20000)

T dòng tiếp theo, mỗi dòng chứa một số nguyên n.

Output

T dòng, mỗi dòng ghi kết quả của test tương ứng.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
4


Được gửi lên bởi:Race with time
Ngày:2009-03-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2013-02-05 16:48:50 a;slkfjasl;fkj
bài này đúng là 1 trong những bài mà mình làm mệt nhất, sau bài MPRIME
2013-02-04 17:31:09 a;slkfjasl;fkj
chạy bị lỗi NZEC là gì vậy trời
2013-01-27 16:19:08 a;slkfjasl;fkj
Làm bị lối SIGSIe gì đó, chán quá
Tự nhiên bị cái lỗi điên điên thế này :((

2013-01-17 16:39:07 moe-chan
time có vẻ chặt ghê ta
2012-12-08 20:01:28 ali33
bỏ readln đi bạn :)
2012-06-12 10:59:46 2ez
Code duoi DPT O(t*n*UCLN(n)) => TLE
2012-03-30 15:41:36 tarzan ngây thơ
code đó có tle ko vậy
2011-12-29 10:12:43 Chế Quốc Hữu
theo mình là bỏ readln ở cuối bài đi
2011-11-23 09:54:50 Acer_98
các bác xem hộ em tí, trong máy thì chạy đc sao post lên lại biên dịch gặp lỗi:|
var i,t,j:longint;
a,b:array[1..2000] of longint;
function ham(a,b:longint):boolean;
var tam:longint;
begin
while b>0 do
begin
tam:=a mod b;
a:=b;
b:=tam;
end;
if a=1 then exit(true) else exit(false);
end;
begin
readln(t);
for i:=1 to t do
begin
readln(a[i]);
b[i]:=0;
end;
for i:=1 to t do
begin
for j:= 1 to a[i] do
if ham(a[i],j)=true then inc(b[i]);
end;
for i:=1 to t do writeln(b[i]);
readln
end.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.