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

And my AC time = 0.968! Can anybody explain to me normal idea of solving this problem?
Posted by Ярославцев Григорий 7 Apr 2004 19:05
Re: And my AC time = 0.968! Can anybody explain to me normal idea of solving this problem?
Posted by buggzy (Ilya Teterin - USU) 7 Apr 2004 19:58
Most of the time spent to find prime divisors. Probably you can optimize it. Try to seek with step=2 instead of 1 for example ;)

Edited by author 07.04.2004 20:04
solution
Posted by Gheorghe Stefan 7 Apr 2004 23:10
Re: solution
Posted by Gheorghe Stefan 7 Apr 2004 23:11
maybe you can compute the primes with Eratostene's sieve...
Re: And my AC time = 0.968! Can anybody explain to me normal idea of solving this problem?
Posted by Ярославцев Григорий 8 Apr 2004 14:37
I think not. I think that the main problem is with the algorithm itself. It is just a little bit optimized
O(sqrt(n)). What is the normal way of finding solutions for
|k1*p - k2*q| = 1?  (k1 and k2 should be found).

Edited by author 08.04.2004 14:42
my algo
Posted by buggzy (Ilya Teterin - USU) 8 Apr 2004 16:26
ap mod bp = cp, c<b, if cp=0 then b=1 and p==gcd(ap, bp)

Recurrent algorithm:

A(1)=p, B(0)=q
C(i)=A(i) mod B(i), A(i+1)=B(i), B(i+1)=C(i)

As gcd(p,q)==1, we get C(i)=1. Then lets write equations sequence:

A(1)-X(1)*B(1)=C(1)
A(2)-X(2)*B(2)=C(2)
...
A(i)-X(i)*B(i)=1

Please note that A(1)==p. Write down coefficient of A(1) in the final equation, and we'll get K such as p*K+q*K2=1. I guess it's the same algorith than called "extended euqlidian" somewhere in this forum.
Re: And my AC time = 0.968! Can anybody explain to me normal idea of solving this problem?
Posted by GodZilla 9 Apr 2004 20:33
Can you tell me the method of finding
k1 and k2 in

a*k1 + b*k2 = 1, where gcd(a,b)=1 ????

Please, help !!!!!!!!!!
Re: And my AC time = 0.968! Can anybody explain to me normal idea of solving this problem?
Posted by Gheorghe Stefan 12 Apr 2004 15:43
Euclid extended algorithme for GCD
Re: my algo
Posted by MU-OI 20 May 2004 19:27
Thank you very much !!!!!
You way is very good !!!!!