Unkoder #05 B: GCD and LCM

CFに出てきそうな問題だ。

問題はこちら。

問題

自然数 a, d, m が与えられる。gcd(a, x) = d, lcm(a, x) = m となるような自然数xを１つ答えよ。そのようなxがなければ-1と出力せよ。

解法

lcm(a, x) = ax / gcd(a, x) であるから、x = md / a と書ける。しかし、md がaで割り切れるとは限らないので x = lcm(md, a) / a とする。あとはこのxで実際に gcd(a, x) = d, lcm(a, x) = m となるかどうかを確認すればいい。

def gcd(a, b): 
    while b: a, b = b, a % b
    return a

def lcm(a, b):
    return a * b / gcd(a, b)

a, d, m = map(int, raw_input().split())
x = lcm(m * d, a) / a
if gcd(a, x) == d and lcm(a, x) == m:
    print x
else:
    print -1

まとめ

lcm, gcd の練習問題としてよくできていると思う。