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 と順番を入れ替えて計算する方が安全です。

long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

/*  lcm (a, b) : 2整数版
    入力:整数 a, b
    出力:aとbの最小公倍数
*/
long long lcm(long long a, long long b) {
    long long d = gcd(a, b);
    return a / d * b;
}

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

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

練習問題