View Single Post
Old 2014-12-27, 18:22   #24
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

72×31 Posts
Default

Quote:
Originally Posted by TeknoHog View Post
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 r|y, but it's still a considerable speedup.
Yes, you are right, but it is still better to check that r|(x^n-1) 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.
R. Gerbicz is offline   Reply With Quote