C++で ax − by = 0 を満たす最小の x と y を求める方法

2つの整数 a と b が与えられたとき、ax − by = 0 を満たす最小の x と y を求めます。例えば、a = 25、b = 35 の場合、x = 7、y = 5 が答えになります。実際に確認すると、25 × 7 = 175、35 × 5 = 175 であり、両辺が等しくなることが分かります。

解法の考え方

この問題を解く鍵となるのは、最小公倍数（LCM）です。a と b の最小公倍数は、「両辺を等しくできる最も小さい値」に相当します。したがって、以下のように x と y を決定すればよいのです。

• x = LCM(a, b) ÷ a
• y = LCM(a, b) ÷ b

こうすることで ax = by = LCM となり、等式が成立します。また、最小公倍数は最大公約数（GCD）を利用して、次の公式で効率よく求められます。

LCM(a, b) = (a × b) / GCD(a, b)

C++での実装例

C++では、標準ライブラリの __gcd() 関数（<algorithm> ヘッダ）を使うことで、最大公約数を簡単に計算できます。以下が具体的なコード例です。

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

void getSmallestXY(int a, int b) {
    int lcm = (a * b) / __gcd(a, b);
    cout << "x = " << lcm / a << "\ny = " << lcm / b;
}

int main() {
    int a = 12, b = 26;
    getSmallestXY(a, b);
}

実行結果

x = 13
y = 6

この例では、a = 12、b = 26 に対して GCD は 2、LCM は 156 となります。したがって x = 156 ÷ 12 = 13、y = 156 ÷ 26 = 6 が求まり、12 × 13 = 26 × 6 = 156 で等式が成立していることが確認できます。

まとめ

ax − by = 0 を満たす最小の x と y を求める問題は、GCD から LCM を計算するだけでシンプルに解決できます。アルゴリズムの計算量は GCD の計算（ユークリッドの互除法）に依存し、O(log(min(a, b))) 程度と非常に効率的です。