More than 3 years have passed since last update.

a, bの最小公倍数と最大公約数の積がabであることを利用した競技プログラミング解法

Last updated at 2020-03-30Posted at 2020-03-28

自然数 $a, b$ の最小公倍数と最大公約数の積が $ab$ であることを利用すると、競技プログラミングで最小公倍数を求める必要が生じたときに役立つ。具体的には、$a, b$ の最小公倍数を $l$ 、最大公約数を $g$ とおくと $ab = gl$ が成り立つため、

l = \frac{ab}{g}

で最小公倍数を求められる。

例えばAtCoderのABC148 C - Snack の解答で役立つ。問題文を見ると分かる通り単に最小公倍数を求める問題である。上式を利用すると解答は以下のように書ける（Pythonによる解答です）。

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

A, B = map(int, input().split())
print(A // gcd(A, B) * B)

補足：a, bの最小公倍数と最大公約数の積がabであることの証明

$a, b$共に $g$の倍数であるため

a = ga' \\
b = gb'

を満たす互いに素な自然数 $a', b'$が存在する。また、$l$ は$a$ の倍数であるため

l = cga'

を満たす自然数 $c$ が存在する。同様にして、

l = dgb'

を満たす自然数 $d$ が存在する。これらより、

cga' = dgb' \\
ca' = db' \\

が成り立ち、$ca'$ は $b'$ の倍数であることがわかる。ここで、$a', b'$ は互いに素であるため $c$ は $b'$ の倍数である。$c$ は最小公倍数 $l$ の因数であるため $c = b'$ である。よって

l = ga'b'

である。両辺に $g$ をかけると

gl = ga'gb' \\
gl = ab

である。以上より証明された。