C++でX = P*A + Q*Bを満たす最小の正整数Xを求める方法

問題文

AとBの値が与えられたとき、次の式を満たす最小の正整数Xを求めることを考えます。

X = P*A + Q*B

ここで、PとQは「0または任意の正・負の整数」を取ることができます。つまり、AとBをそれぞれ何倍かして足し合わせた結果の中から、最も小さい正の整数を見つける問題です。

例

A = 2、B = 4 の場合、答えは 2 になります。
たとえば P = 1、Q = 0 とすると X = 2*1 + 4*0 = 2 となり、これより小さい正の整数は作れないため、答えは2です。

アルゴリズム

この問題は、ベズーの等式（Bézout's identity）と呼ばれる数論の定理を使うことで解くことができます。

• ベズーの等式によると、X = P*A + Q*B の形で表せる最小の正整数は、必ず A と B の最大公約数（GCD）に一致します。
• したがって、PやQを総当たりで探す必要はなく、AとBのGCDを計算するだけで答えが得られます。

GCDの計算には、効率的な手法として知られるユークリッドの互除法を使用します。

実装例（C++）

#include <iostream>
using namespace std;

int getGcd(int a, int b) {
    if (a == 0) {
        return b;
    }
    return getGcd(b % a, a);
}

int main() {
    cout << "Answer = " << getGcd(2, 4) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Answer = 2

まとめ

X = P*A + Q*B を満たす最小の正整数Xは、AとBの最大公約数に等しいという性質を利用すれば、ユークリッドの互除法によって O(log(min(A, B))) の計算量で効率的に求められます。PとQを直接探索する必要がないため、非常にシンプルかつ高速な解法となります。