| Submit | All submissions | Best solutions | Back to list |
INVPHI - Smallest Inverse Euler Totient Function |
This task is the inverse of ETF problem, given an integer n find smallest integer i such that φ(i)=n, where φ denotes Euler's totient function.
Input
The first line is an integer T (1 ≤ T ≤ 100,000), denoting the number of test cases. Then, T test cases follow.
For each test case, there is an integer n (1 ≤ n ≤ 100,000,000) written in one line. (one integer per line)
Output
For each test case, output Smallest Inverse Euler's Totient Function of n. if n doesn't have inverse, output -1.
Example
Input: 5 10 20 30 40 50 Output: 11 25 31 41 -1
Time Limit ≈ 3*(My Program Top Speed)
| Added by: | Tjandra Satria Gunawan |
| Date: | 2012-09-28 |
| Time limit: | 20s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own Problem |
hide comments
|
||||||
|
2012-10-13 09:20:23 Akhil Mittal
for which test case my code gives wrong answer??..Submission Id:-7842540 Got AC..:) Last edit: 2012-10-13 09:37:07 |
||||||
|
2012-10-11 15:46:17 Ehor Nechiporenko
So great task )) Ans: Thanks :) Last edit: 2012-10-11 16:16:42 |
||||||
|
2012-10-04 02:00:40 mehmetin
Can you say what is the highest value for i (for n <= 100 million)? Ans: highest value: i=202918035, when n=99683840 Last edit: 2012-10-04 11:38:37 |
||||||
|
2012-09-30 13:22:07 Sameer Jain
The cube is really fast. My brute force algo takes 50 second on my PC but works in just 12 sec here Ans: yes, the cube is faster than my PC too, my semi-brute-force algo is 16s on my PC, and 6.83s here on cube processor. Congratulations, now you may try the harder version of this problem type: Smallest Inverse Sum of Divisors :-) Last edit: 2012-09-30 15:00:43 |
||||||
|
2012-09-28 17:44:18 (Tjandra Satria Gunawan)(曾毅昆)
Well, now this problem running at cube processor, I want to know how fast you are \(^_^)/ |
||||||
RSS