Quote:
Originally Posted by TeknoHog
Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case ry, but it's still a considerable speedup.

Yes, you are right, but it is still better to check that r(x^n1) is true or not. These methods just working, for a recent similar problem see
http://www.spoj.com/problems/PRIMPOW2/ this is even a harder problem since there half of the input is a perfect power.