Обсуждение @ 1430. Преступление и наказание @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

AC Rauf Agayev 23 мар 2011 23:01

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 sklyack 27 авг 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 -XraY- 18 ноя 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 sklyack 27 ноя 2011 00:06

Thank you.

Обсуждение задачи 1430. Преступление и наказание