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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
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.
Name |
---|
Here is the strightforward solution. We can sieve the phi values up to 202918035 (please, see comments to the problem statement).
Also you can note that almost all resulting numbers are odd with three exceptions, so we can sieve only odd values:
Though I do not know how can we achieve 0.04 sec or how will it run in Java.
Thx for your help,but I did the same thing in java but its not working!
Hm, did you read this? Also you can apply segmented phi sieve (as for spoj ETFS problem).
Thanks for your time, I submitted the code in C, it worked fine!!