http://www.spoj.com/problems/ENIGMATH/
Here we need to notice that if A*x - B*y =0 then for A=y and B=x the equation is true. We could have just printed the numbers and finish but the problem asks for the minimum number and for example for this case 2*x-4*y=0 the minimum answer is not 4 and 2 but 2 and 1 :). So here is what we should notice the right formula is x=B/GCD(A,B) and y=A/GCD(A,B) where GCD means the greatest common divisor of numbers A and B. You can find more info about calculating GCD fast here.
Here we need to notice that if A*x - B*y =0 then for A=y and B=x the equation is true. We could have just printed the numbers and finish but the problem asks for the minimum number and for example for this case 2*x-4*y=0 the minimum answer is not 4 and 2 but 2 and 1 :). So here is what we should notice the right formula is x=B/GCD(A,B) and y=A/GCD(A,B) where GCD means the greatest common divisor of numbers A and B. You can find more info about calculating GCD fast here.
No comments:
Post a Comment