C++で有理数の最小公倍数（LCM）を求める方法

本記事では、有理数（分数）の最小公倍数（LCM）を求める方法を解説します。例えば、{2/7, 3/14, 5/3} という有理数のリストが与えられた場合、そのLCMは 30/1 となります。

有理数のLCMを求める公式

この問題を解くには、まずすべての分子のLCM（最小公倍数）を計算し、次にすべての分母のGCD（最大公約数）を計算します。有理数のLCMは、次の式で表されます。

$$LCM = \frac{すべての分子のLCM}{すべての分母のGCD}$$

各分数の倍数となる有理数は、分子がすべての分子の公倍数であり、かつ分母がすべての分母の公約数である必要があります。その中で最小のものが「分子のLCM ÷ 分母のGCD」になるというわけです。

C++による実装例

以下は、このアルゴリズムをC++で実装したサンプルコードです。分数は pair<int, int>（分子, 分母）として扱っています。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 最大公約数を使って最小公倍数を求める
int LCM(int a, int b) {
    return (a * b) / (__gcd(a, b));
}

// すべての分子のLCMを計算する
int numeratorLCM(vector<pair<int, int> > vect) {
    int result = vect[0].first;
    for (int i = 1; i < vect.size(); i++)
        result = LCM(vect[i].first, result);
    return result;
}

// すべての分母のGCDを計算する
int denominatorGCD(vector<pair<int, int> vect) {
    int res = vect[0].second;
    for (int i = 1; i < vect.size(); i++)
        res = __gcd(vect[i].second, res);
    return res;
}

// 有理数のLCMを表示する
void rationalLCM(vector<pair<int, int> > vect) {
    cout << numeratorLCM(vect) << "/" << denominatorGCD(vect);
}

int main() {
    vector<pair<int, int> > vect;
    vect.push_back(make_pair(2, 7));
    vect.push_back(make_pair(3, 14));
    vect.push_back(make_pair(5, 3));
    cout << "有理数のLCM: ";
    rationalLCM(vect);
}

実行結果

有理数のLCM: 30/1

コードの解説

プログラムの処理の流れは以下の通りです。

1. LCM関数：2つの整数の最小公倍数を「a × b ÷ GCD(a, b)」で求めます。GCC拡張の __gcd() を利用しています。
2. numeratorLCM関数：ベクターに格納されたすべての分数の分子（first）に対して、先頭から順にLCMを畳み込んで計算します。
3. denominatorGCD関数：すべての分母（second）に対して、先頭から順にGCDを畳み込んで計算します。
4. rationalLCM関数：分子のLCMと分母のGCDを組み合わせ、「分子のLCM / 分母のGCD」の形式で結果を出力します。

検算してみましょう。分子 2, 3, 5 のLCMは 30、分母 7, 14, 3 のGCDは 1 となるため、答えは 30/1 となり、実行結果と一致します。

計算量と注意点

n個の有理数を処理する場合、各要素ごとにGCD計算（ユークリッドの互除法）を行うため、全体の時間計算量は O(n log M) となります（M は扱う数値の最大値）。ただし、LCMの計算では分子同士の積が大きくなりやすいため、大きな数を扱う場合は long long 型の使用やオーバーフロー対策を検討してください。また、__gcd() はGCC固有の関数のため、移植性を重視する場合はC++17で標準化された std::gcd() を使うとよいでしょう。