Discussion @ 1430. Crime and Punishment @ Timus Online Judge

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

Posted by hoan 30 Dec 2010 19:42

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

Posted by bsu.mmf.team 31 Dec 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!!!

Posted by hoan 3 Jan 2011 15:16

thanks so much!!!

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

Posted by bsu.mmf.team 3 Jan 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!!!

Posted by hoan 3 Jan 2011 19:57

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

Discussion of Problem 1430. Crime and Punishment