SLIMSHADYNICK's blog

Inverse of Euler totient function

By SLIMSHADYNICK, history, 5 years ago, In English

There's this problem INVPHI on spoj, I have not been able to solve it. I have been getting NZEC runtime error. Could anyone tell me how to approach as I feel I have exceeded the memory limitations.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here is the strightforward solution. We can sieve the phi values up to 202918035 (please, see comments to the problem statement).

Code, 9.35sec, 1157M

Also you can note that almost all resulting numbers are odd with three exceptions, so we can sieve only odd values:

Code, 4.65sec, 770M

Though I do not know how can we achieve 0.04 sec or how will it run in Java.

→ Reply