ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1204. Idempotents

Can someone explain this problem to me?
Posted by Stefan Ciobaca 22 Mar 2002 03:41
I can have my program solve it in sqrt(n) but this is not good enough.
Please tell me how to optimize. 10x in advance
Re: Can someone explain this problem to me?
Posted by MadPsyentist/Sam 22 Mar 2002 18:04
As I guess, your O(sqrt(n)) time is from finding ap+bq=1 , right?
If so , you can use extended Euclidean algorithm (one which find GCD)
to solve this equation.
Re: Can someone explain this problem to me?
Posted by Dragon 19 Oct 2002 15:20
Right! I got AC! (the GCD of p and q is 1!!!!!!!)