I have been working on both the problems lately(both being the same problem but with different constraints).
I need some directions/hints about proceeding further.
I have submitted a solution to IITKWPCQ in python. It is giving WA.
Set of Test cases tried -
1. I tried it on all integers from 1-30000
2. First 10000 primes(10000th prime -> 104729)
3. each of the numbers in point 2 raised to the power of 2,3,4 (power 4 gets sufficiently larger than the test limit)
4. all pseudo primes(PSPs) upto 2^64. Yes ! I downloaded the list of pseudo primes(800mb compressed data,2.5 GB on uncompressing) from - cecm.sfu.ca/Pseudoprimes/ . Ran it for the whole day !!
. There are 72875460 base 2 PSPs.
Result of Test 4 - all of them gave "1" as the answer except only 2 numbers(that were perfect squares) - 1194648 and 12327121. Huhh !!!
All the above test cases give the correct answer.
After doing all that when I run my code, it gives WA. Am I missing any important test case?
I can share the solution/approach too. Any help is appreciated.