2つの自然数の最小公倍数(LCM)を求めるアルゴリズム
最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。
最小公倍数は、最大公約数を利用することで簡単に求めることができます。
2つの自然数の最小公倍数
2つの自然数 \(a, b\) の最小公倍数：
- a と b の最大公約数を d とする
- \(\frac{a \times b} {d}\) が最小公倍数
※ このアルゴリズムは、「２つの自然数の積はその最小公倍数と最大公約数の積に等しくなる」という以下の数式を利用しています。（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つずつ最小公倍数を求める」という方針でうまくいきます。