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

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!!

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);

Thank you.