TIP3 - Totient in permutation (hard)

no tags 

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.

Input

There is only one number M.

Output

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.

Example

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 which 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 which 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 which 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.

Constraints

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.)


hide comments
Min_25: 2016-06-11 18:11:04

Note:
We should not use "while (~scanf(...))" in this problem.
It will cause TLE.

=(Francky)=> I guess it's the 'interactive' part of the judge that makes it work like that. Congrats again for your AC.

Re: Thank you!

Last edit: 2016-06-12 12:20:21
[Lakshman]: 2015-07-30 15:45:13

I think the the problem has been fixed!!
Now we can try this.

=(Francky)=> Yes it's true !!! At last ;-) I really don't know what was the bug and who solved it ! Many thanks for your spot. Rejudge for all submissions in the 'fail' period.
Edit : I think Michał solved the bug ! ? ! Thanks !!!

Last edit: 2015-07-30 21:11:22
Francky: 2014-06-21 11:16:49

@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, ...
Internal error is raised by « multiple definition of `spoj_p_in' », ...

edit (15-11-2014) : According to admins, the issue should be fixed with next language upgrade. Please be patient.

Last edit: 2014-11-15 23:59:48
Viplov Jain: 2014-06-21 07:03:51

@Francky my code is giving internal error.what does that mean?

@Francky thanks for reply.

Last edit: 2014-06-21 16:19:23
Francky: 2014-03-09 21:28:38

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...
Sorry for inconvenience.
Edit : it seems not affect some other interactive problems. Strange. I didn't change anything !!!

Last edit: 2014-03-09 21:47:38
Michael Kharitonov: 2013-03-14 22:21:06

Why half of my submissions are disqualified? I know some of them are wrong, I kinda hope judge will turn them down, not you;-)
--ans--> You had disqualified those ones, rejudge ignore that fact, so I manually disqualified those ones - they all led to SIGABRT or compil-error by the way. Do you want them to be rejudged ? I hope I did the best.
--forw--> I disqualified only CE, RE just tells that solution might not have found or not be optimal, that's all. Redjudge not needed, was curious as always. Nothing changed after rejudge, I have tests that break my solutions, but they are very rare;-)
--ans(francky)--> You did a really good job, some weaknesses can be a part of any problem, even a HARD one like this one. One can't imagine all solutions for this problem...

Last edit: 2013-03-19 11:27:50
Michael Kharitonov: 2013-03-14 21:52:51

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.
--ans--> Congratulations.
edit : Some more test cases added, rejudge done. 10 different judges.

Last edit: 2013-03-14 21:52:24

Added by:Francky
Date:2013-01-06
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TIP2