配列の全ての要素(N個)の最小公倍数(LCM)を求めるアルゴリズム
配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。
Input: a = {1, 3, 6, 8, 12}
output: 24
アルゴリズム
N個の自然数の最小公倍数:
- リスト {\(a_1, a_2, a_3,…, a_N\)} の要素数が 1 つになるまで以下を繰り返す
- リストから2つ選んで最小公倍数 lcm を計算し、リストに加える
- 残った 1 つが全体の最小公倍数
※ 複数の自然数の最小公倍数を求める場合でも、2つずつ最小公倍数を求めていけば、最終的に全ての自然数の最小公倍数が求まります。
※ 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; }
ディスカッション
コメント一覧
まだ、コメントがありません