|
|
back to boardAC Given A B N D=GCD(A,B); then N/=D and N*=D and N/=D;because we must find closed number to N; A/=D; B/=D; then full search if(A>B) for(i=0;i<=N/A;i++){type here equation Ai+By=N, try to find x and y} else for(i=0;i<=N/B;i++){type here equation Ax+Bi=N , try to find x and y} *trick:in loop, if Ax+By=N then break,that means we have already found number.. Edited by author 24.03.2011 01:44 Re: AC Posted by sklyack 27 Aug 2011 01:34 I did how you said, and when I tried to pass this solution without trick, I got TL#10, with trick got AC in 0.031 sec. I really don't understand, how this trick can give so impressive speed-up? Explain me pls!! Re: AC Posted by -XraY- 18 Nov 2011 23:56 Let's suppose A >= B, (A, B) = 1; Then there is such (0 <= i < b) that (a * i) % b = (N % b). On the other hand, i <= N / a. So, i <= min(N / a, b - 1) <= min(N / a, a - 1) <= sqrt(n); Re: AC Posted by sklyack 27 Nov 2011 00:06 Thank you. |
|
|