配列の全ての要素(N個)の最小公倍数(LCM)を求めるアルゴリズム

2020年3月20日数学最小公倍数,配列,結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, 3, 6, 8, 12}
output: 24

アルゴリズム

N個の自然数の最小公倍数：

  1. リスト {\(a_1, a_2, a_3,…, a_N\)} の要素数が 1 つになるまで以下を繰り返す
    • リストから2つ選んで最小公倍数 lcm を計算し、リストに加える
  2. 残った 1 つが全体の最小公倍数

※ 複数の自然数の最小公倍数を求める場合でも、2つずつ最小公倍数を求めていけば、最終的に全ての自然数の最小公倍数が求まります。
※ ２つの場合の最小公倍数の求め方はこちらを参照

計算量

  • \(O(N \log( a’ ) )\)　（\(a’\) は二番目に大きい数）

2つの場合の最小公倍数の計算を N-1 回繰り返すことになります。

C++での実装例

N個の最小公倍数は非常に大きな数になる可能性があるので、使用する際はオーバーフローにならないか注意しましょう。

※ gcd はC++17 から標準ライブラリに追加されています。以下は C++14 での例です。

#include <bits/stdc++.h>
using namespace std;

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

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

/* lcm (vec) : ベクトルでの多整数版
    入力：整数のベクトル vec
    出力：すべての要素の最小公倍数
*/
long long lcm(const vector<long long> &vec) {
    long long l = vec[0];
    for (int i = 0; i < vec.size() - 1; i++) {
        l = lcm2(l, vec[i + 1]);
    }
    return l;
}

練習問題

数学最小公倍数,配列,結合則