TIP3 - Totient in permutation (hard)
In number theory, Euler's totient (or PHI function), is an arithmetic function that counts the number of positive integers less than or equal to a positive integer N that are relatively prime to this number N.
That is, if N is a positive integer, then PHI(N) is the number of integers K for which GCD(N, K) = 1 and 1 ≤ K ≤ N. We denote GCD the Greatest Common Divisor. For example, we have PHI(9)=6.
Interestingly, PHI(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
There is only one number M.
For the given M, you have to print on a single line the value of N, for which 1 < N < M, PHI(N) is a permutation of N and the ratio N/PHI(N) produces a minimum. If there's several answers output the greatest, or if need, "No solution." without quotes. Leading zeros are not allowed for integers greater than 0.
Input: 22 Output: 21 Input: 222 Output: 63 Input: 2222 Output: 291
Explanations : For the first case, in the range ]1..22[, the lonely number n for witch phi(n) is in permutations(n) is 21, (we have phi(21)=12). So the answer is obviously 21. For the second case, in the range ]1..222[, there's two numbers n for witch phi(n) is in permutations(n), we have phi(21)=12 and phi(63)=36. But as 63/36 is equal to 21/12, we're taking the greater : 63. For the third case, in the range ]1..2222[, there's four numbers n for witch phi(n) is in permutations(n), phi(21)=12, phi(63)=36, phi(291)=192 and phi(502)=250. Within those solutions 291/192 is the minimum, we output 291.
1 < M < 10^27
If you got TLE, you should consider before TIP2. Enjoy. Warning : don't try to investigate the input number, judge is strict and interactive ; test case is randomly changing, staying equivalent in difficulty. Please don't use spurious spaces and end your answer with '\n' ; e.g. "21\n" awaited for the sample. There is many ways to optimize the solution for this problem, to get AC here, you'll need to find many of them. Time limit allows python3 solutions. There is different judges, time is the sum of them. (Edit 2017-02-11, after compiler changes : my Py3 solution ends in 25s, approx 2.5s per file, 10 files.)
I think the the problem has been fixed!!
@Viplov : I will write to admin (third time) for this issue. I'm sorry for inconvenience. I'll tell you soon if your code can get AC, WA or TLE, ...
@Francky my code is giving internal error.what does that mean?
It seems 'interactive problems' have a bug, it's no longer possible to submit here, it causes 'internal error'. I will change my judge. Thanks to Mitch and Robert who confirmed the bug. I would like to use this kind of judge for my new problems, I'll use instead several IO files. Here too in the future. It will need a rejudge, in time...
Why half of my submissions are disqualified? I know some of them are wrong, I kinda hope judge will turn them down, not you;-)
Test cases are not equivalent at least for my solution. I suggest at least 10 random cases, the results will be more reliable, plus (hard optimum + C), C - small const.