ETF - Euler Totient Function
In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.
Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.
Input
First line contains an integer T, the number of test cases. (T <= 20000)
T following lines, each contains an integer n.
Output
T lines, one for the result of each test case.
Example
Input: 5 1 2 3 4 5 Output: 1 1 2 2 4
hide comments
|
mrmajumder:
2019-11-27 11:55:18
Try to implement O(sqrt(n)) ;) |
|
lizmurray:
2019-11-20 08:20:36
How can i avoid tle in java?
|
|
sicklesplit:
2019-09-11 19:13:33
Was using long long and getting wa, Use float and then type convert to get AC |
|
prabhat7298:
2019-09-09 05:10:04
Can be done in O(n) using linear sieve |
|
sidharth20:
2019-08-14 07:10:46
AC in 100th go Last edit: 2019-08-14 07:14:46 |
|
sanket17:
2019-07-08 09:04:00
By using seive in c++ i m getting TLE
|
|
sid779:
2019-07-01 09:47:21
AC in one go using Euler's totient function. |
|
fill32:
2019-06-19 10:00:09
for python, don't use sieve8 cause import numpy takes alot of time, use naive sive with max 10^4 is enough to get AC. |
|
anmol_9557:
2019-06-18 19:23:03
AC in one go! just go cp-algorithm for implementation in case neede. |
|
aj_254:
2019-05-13 20:40:10
after many optimization solved in python 0.10 sec ez pz lemon squezy used standard i/o and euler sieve and you definetely get ac |
| Added by: | Race with time |
| Date: | 2009-03-27 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
RSS