Friday, December 25, 2009

11388 - GCD LCM - UVA

Mathematics

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

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...