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

please give me idea to solve this problem, thanks!!!

Послано hoan 30 дек 2010 19:42

Re: please give me idea to solve this problem, thanks!!!

Послано bsu.mmf.team 31 дек 2010 04:14

Just full search. ~O(sqrt(N)) in the worst case. To avoid TL before search do:
C = GCD(A,B);
A /= C;
B /= C;
N -= (N%C);
Think why you always can do this.
GOOD LUCK!

Re: please give me idea to solve this problem, thanks!!!

Послано hoan 3 янв 2011 15:16

thanks so much!!!

Re: please give me idea to solve this problem, thanks!!!

Послано bsu.mmf.team 3 янв 2011 16:33

Oh! I forgot, that after that N must be divided by C too :)

Re: please give me idea to solve this problem, thanks!!!

Послано hoan 3 янв 2011 19:57

got AC now.
thanx again & HAPPY NEW YEAR!!!

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