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)
hide comments
Akhil Mittal:
2012-10-13 09:20:23
for which test case my code gives wrong answer??..Submission Id:-7842540
|
|
Ehor Nechiporenko:
2012-10-11 15:46:17
So great task ))
|
|
mehmetin:
2012-10-04 02:00:40
Can you say what is the highest value for i (for n <= 100 million)?
|
|
Sameer Jain:
2012-09-30 13:22:07
The cube is really fast. My brute force algo takes 50 second on my PC but works in just 12 sec here
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-09-28 17:44:18
Well, now this problem running at cube processor, I want to know how fast you are \(^_^)/ |
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 |