Friday, December 25, 2009

11388 - GCD LCM - UVA


As you can see in the problem description, you have to find numbers a & b such that (a, b) = G and [a, b] = L and also it has mentioned that if there is more than one pair satisfying the condition, output the pair for which number a is minimized. It's a very easy problem, you have to figure out whether the remainder of L / G is equal to zero or not, if so, your answer is G & L otherwise you have to output -1. Note that in the worst case (a, b) = a and these inequalities always satisfy.
(a, b) --->>> GCD of a & b
[a, b] --->>> LCM of a & b
(a, b) <= a (a, b) <= b [a, b] >= a
[a, b] >= b