2つの自然数の最小公倍数(LCM)を求めるアルゴリズム

2020年3月1日数学最大公約数, 競プロ, ユークリッドの互除法, 最小公倍数

最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。

最小公倍数は、最大公約数を利用することで簡単に求めることができます。

2つの自然数の最小公倍数

2つの自然数 \(a, b\) の最小公倍数:

  1. a と b の最大公約数を d とする
  2. \(\frac{a \times b} {d}\) が最小公倍数

※ このアルゴリズムは、「2つの自然数の積はその最小公倍数と最大公約数の積に等しくなる」という以下の数式を利用しています。(lcm: 最小公倍数、gcd: 最大公約数)

$$ a \times b= lcm \times gcd$$

※ 最大公約数の求め方はこちらを参照

計算量

  • \(O(log ~min(a,b))\)

最大公約数を求めるのに、\(O(log ~min(a,b))\) だけ必要で、後は定数時間で計算をすることができます。

C++での実装例

a*b/d を計算する際は、a*b の値が非常に大きくなってオーバーフローしてしまう可能性があるので、a/d*b と順番を入れ替えて計算する方が安全です。

参考:N個の最小公倍数の求め方

N個の要素に対する最小公倍数を求める場合は、「2つずつ最小公倍数を求める」という方針でうまくいきます。

練習問題