SPOJ.com - Problem INVPHI

INVPHI - Smallest Inverse Euler Totient Function

#totient

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.

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)

For each test case, output Smallest Inverse Euler's Totient Function of n. if n doesn't have inverse, output -1.

Input:
5
10
20
30
40
50

Output:
11
25
31
41
-1

Time Limit ≈ 3*(My Program Top Speed)

Submit solution!

< Previous 1 2 3 Next >

	Akhil Mittal: 2012-10-13 09:20:23 for which test case my code gives wrong answer??..Submission Id:-7842540 Got AC..:) Last edit: 2012-10-13 09:37:07
	Ehor Nechiporenko: 2012-10-11 15:46:17 So great task )) Ans: Thanks :) Last edit: 2012-10-11 16:16:42
	mehmetin: 2012-10-04 02:00:40 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
	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 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
	(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 \(^_^)/