| 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
|
||||||
|
2023-08-28 05:39:02
Nice problem. After some brainstorming I able to get AC in 2. Learned something new. Thanks. |
||||||
|
2021-05-22 04:40:02
How to prove that the answer is bounded by 2e8? |
||||||
|
2020-03-10 19:24:33
Anyone Getting nzec in java? My code is running fine locally! |
||||||
|
2019-12-07 12:47:56
calculate phi value upto 160126035 |
||||||
|
2019-11-29 16:33:09
How to find the value of totient of a number greater than 10^9? |
||||||
|
2018-09-04 13:31:26
Getting WA, some test cases please. For n = 1 , case the result should be 1, right? |
||||||
|
2018-05-31 11:44:31
@admin Why I'm getting runtime error for my this sol'n 21755292? |
||||||
|
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 :) |
||||||
|
2015-06-30 13:22:12 Chetan
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! :/ |
||||||
|
2014-01-08 18:52:48 [Lakshman]
@(Tjandra Satria Gunawan)(曾毅昆) Can you please tell me why I am getting WA, I think My algorithm is correct. Please help. |
||||||
RSS