1.4.2. 最小公倍数¶
Code: gcd_and_lcm.py
Test: test_gcd_and_lcm.py
最小公倍数とは¶
Least common multiple (Wikipedea)
2つ以上の正の整数について、それぞれの正の倍数から共通する数を取り出したときの、最も小さな数のことをいう。
例えば、 \(12, 18, 24\) の最小公倍数は \(72\) である。実際、それぞれの倍数を列挙すると
12の倍数 \(12, 24, 36, 48, 60, \mathbf{72}, \ldots\)
18の倍数 \(18, 36, 54, \mathbf{72}, 90, \ldots\)
24の倍数 \(24, 48, \mathbf{72}, 96, \ldots\)
となり、共通の倍数のうち最小の数は \(72\) である。
法則¶
最小公倍数は交換則と結合則が成り立つ。
交換則 \(\mathrm{lcm}(a, b) = \mathrm{lcm}(b, a)\)
結合則 \(\mathrm{lcm}(a, \mathrm{lcm}(b, c)) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)\)
また、2数の最大公約数と最小公倍数には次の関係がある。これは3数以上では成り立たない。
\(ab = \gcd(a, b) \cdot \mathrm{lcm}(a, b)\)
正の倍数に \(0\) が含まれないので、 \(0\) を含む最小公倍数は定義されない。
ただし、便宜上次のように定義することがある。
\(\mathrm{lcm}(a, 0) = 0\)
実装¶
概要¶
複数の整数の最小公倍数を求める。
実装のポイント¶
最小公倍数に関して、 \(0\) を含む定義を採用した。
計算量¶
lcm(a, b)\(\mathcal{O}(\log{\min(a, b)})\)
コード¶
[1]:
import math
def lcm(a: int, *args: int) -> int:
for b in args:
if b == 0:
a = 0
else:
a = a * b // math.gcd(a, b)
return a