Submit  All submissions  Best solutions  Back to list 
TOTIENT  Totient function 
Wersja polska  English version 
In number theory φ(n) is defined to be the number of positive integers less than or equal to n that are coprime to n.
Input
The first line of the standard input contains one integer t (t<101) which is the number of test cases.
In each of the next t lines there is one integer n (n<2*10^9).
Output
For each test, print φ(n).
Example
Input:
3
1
6
100
Output:
1
2
40
Added by:  Piotr Ką kol 
Date:  20100214 
Time limit:  9.687s19.58s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC SCM qobi VB.NET 
hide comments
20140310 10:47:49 Piotr KÄ…kol
Thanks for the info. Fixed. Seems spoj.pl is down. 

20140305 14:21:22 Hallvard Norheim Bø
@Piotr: I found the reason for failure. Math.factor() only does trial divison by the first 1024 primes! Also note that all links on the SHORTEN pages which starts with spoj.pl has stopped working. On the Links page, the RSS feed, etc. 

20140301 02:11:11 Piotr KÄ…kol
You have WA for 490645137. 

20140227 18:31:53 Hallvard Norheim Bø
@Piotr: for what input is my latest Pike submission (#11149257) wrong? 

20140214 01:55:38 Piotr KÄ…kol
I made a rejudge after adding a test with some small numbers. Feel ashamed for not checking boundary cases, sorry. 

20100810 13:46:00 Piotr KÄ…kol
Number of test cases was reduced to 100. 

20100401 16:36:51 numerix
Thanks! 

20100329 14:46:50 Piotr KÄ…kol
I changed time limit from 10 to 15 sec. ;) // And from 15 to 20. :) Last edit: 20100518 07:31:52 