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.


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 ineger per line)


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





Time Limit ≈ 3*(My Program Top Speed)


See also: Another problem added by Tjandra Satria Gunawan

hide comments
cat_got_bored: 2016-12-03 17:42:56

The solution is straightforward but there are some pitfalls. some tips :
1) Don't do binary search. Sorting will take too much time (TLE).
2)Check for n=1.
3)Use all int arrays (Or will get SEGKILL). inside loops, use long long to avoid overflow.
3)Finally, here n means the the value of totient function, you need to find x. where, ETF(x) = n. Even though, n will be at most 10^8, you need to find x, which can be bigger than 10^8.
4)The maximum x for this problem is 202918035, when n=99683840.
Thanks to problemsetter, Nice problem :)

Chetan: 2015-06-30 13:22:12

Please Help me out here with SPOJ submission 14571312
I've no idea why I keep getting SIGSEGV or SIGKILL here.
I've provided the correct limiting conditions, according to me! :/

[Lakshman]: 2014-01-08 18:52:48

@(Tjandra Satria Gunawan)(曾毅昆)
Can you please tell me why I am getting WA, I think My algorithm is correct.
Please help.

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
anurag garg: 2013-12-29 04:28:12

Last edit: 2013-12-29 04:28:38
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

Added by:Tjandra Satria Gunawan
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Own Problem