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.

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)

Submit solution!

hide comments

< Previous 1 2 3 Next >

	anurag garg: 2013-12-29 04:28:12 @(Tjandra Satria Gunawan)(曾毅昆) my code is giving WA Edit: AC after 20 or so many WA very nice question learned so many new concepts Last edit: 2014-01-07 20:41:13
	Sandeep Pathry: 2013-07-12 16:23:38 Finally!!! AC... n=1 case costed me 15 WAs... :D Last edit: 2013-07-13 08:28:38
	Ritam Shukla: 2013-01-19 10:30:39 Though i have a doubt. Why is it that even if i try to run my accepted solution on ideone, it gives a runtime error SIGKILL? Is it that memory limit there is very tight? And is there any special option available there that enables us to use the Cube? Ans: I don't know... but seems that memory limit for ideone still 256 MB, for more info about this click here. Last edit: 2013-01-19 11:17:22
	Ritam Shukla: 2013-01-18 21:22:57 One of the finest tasks I've ever done! Great job, Tjandra. Keep it up. :) Ans: Thanks for your appreciation :-) Last edit: 2013-01-19 11:18:15
	Ritam Shukla: 2013-01-12 20:16:19 No, not a super computer. Just a Hyperthreaded Intel Core i7-3770 4 cores 8 threads with turbo boost 3.9GHz. (I'm using without turbo currently, so I get about 3.5GHz) I think ONE MUST NOT COMPARE IDEONE WITH THE CUBE. What I believe is that ideone is equivalent to the Pyramid cluster of SPOJ, so it is bound to take >15 sec and we know that it cannot be used to time a code which takes more than 15s on Pyramid(correct me if i'm wrong). Though I just checked it out there. Anyway thanks for ur help i'll try something different later on. Ans: Now Ideone using cube cluster.. I've tested it, and it really fast, faster than my computer, but slower than your computer of course :-P Last edit: 2013-01-13 07:11:17
	Ritam Shukla: 2013-01-12 10:05:34 @Tjandra, if you see my code, you'll realize that I precompute just once for an input file of any size, and the subsequent processing of the individual test cases (whatever their number may be) won't take more than 1-2 seconds. Moreover, the initial precomputation takes ~12-13 seconds on my PC. Even if there is some error in the logic, with so many people telling that the Cube is so fast, I expected a WA. As far as your question is concerned, I'd like to answer: Yes, I created an input file with random inputs and I DID GET AN ANSWER IN <15 seconds. Could you just go through my solution once (ID=8463302) and suggest something ? I'd be grateful. Thanks for replying btw. :) Ans: Which super computer you're using? I test your code on my own computer and it give ~30s.. My suggestion: try running your code on Ideone, and see how long it take... Last edit: 2013-01-12 16:54:33
	Ritam Shukla: 2013-01-12 07:32:15 My brute force approach works on my system in <15 seconds but gives Time Limit Exceeded here on Cube cluster. :( Ans: did you try with 100.000 random test cases? Last edit: 2013-01-12 08:27:58
	Snehasish Roy ;): 2012-12-26 17:40:03 @Tjandra: Kindly tell whats the required complexity for the solution to be AC ? Are my bounds of searching more than required ? Or is there any other method I should try ? Kindly tell .. Ans: Yes, there is another faster method than precomputing answer, but if you want to precompute the answer, you must avoid repeated calculation to get AC. RE-> Thanks for the reply. But call to the function ETF() is made only once, which does the precomputation. How I am doing repeated calculations? Kindly see my submission id: 8354825 Is this what you are asking for or I am misinterpreting ? Kindly suggest. Ans2: Yes, when you call ETF() no repeated calculation, but when you compute the inverse of ETF() "fill the memoization[] array when running each test case" you did so many repeated or useless calculation.. RE-> Thanks Tjandra for helping me out. Finally got AC. Thanks a lot again. Ans3: Good.. Last edit: 2012-12-27 15:04:28
	Ashish Lavania: 2012-12-19 08:36:22 which compilers do you guys use? I cant check my solution on any of the ones I have
	Ashish Lavania: 2012-12-14 16:00:35 Where am I getting WA?? Please tell me ASAP <u><b>Ans:</b></u> Seems that overflow occured, your program give correct answer only for small n: n< sqrt(2^31) = 46340. Be careful when you multiply two 32-bit signed integer ;-) Thanks but still WA? Guess Ill have to rethink Last edit: 2012-12-15 06:07:39

Submit solution!

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