【C++】合計と最大公約数（GCD）が与えられた2つの数を求める方法

この記事では、2つの数 a と b の合計（sum）と最大公約数（GCD）が与えられたときに、元の2つの数を復元する方法を解説します。条件を満たす組み合わせが存在しない場合は -1 を返します。

例えば、合計が 6、GCDが 2 とすると、答えは 4 と 2 になります（4 + 2 = 6、gcd(4, 2) = 2 を満たすため）。

考え方（アプローチ）

GCDが分かっているということは、2つの数がどちらもGCDの倍数であることが確定します。この性質を利用すると、次の手順で答えを導き出せます。

• 候補の生成： 片方の数をGCDそのものと仮定すると、もう片方は「合計 − GCD」となります。

• 検証： 仮定した2つの数の実際のGCDを計算し、与えられたGCDと一致するかどうかを確認します。また、合計がGCDと等しい場合（＝もう片方が0になる場合）は不正なペアとなるため除外します。

• 出力： 条件を満たしていれば小さい方・大きい方の順で2つの数を出力し、満たさなければ -1 を出力します（そのような数の組は存在しないため）。

C++での実装例

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

void printTwoNumbers(int s, int g) {
    if (__gcd(g, s - g) == g && s != g)
        cout << "first number = " << min(g, s - g)
              << "\nsecond number = " << s - min(g, s - g) << endl;
    else
        cout << -1 << endl;
}

int main() {
    int sum = 6;
    int gcd = 2;
    printTwoNumbers(sum, gcd);
}

実行結果

first number = 2
second number = 4

コードのポイント

• __gcd(g, s - g) はGCCが提供するユーティリティ関数で、2つの整数の最大公約数を返します。C++17以降では標準ライブラリの std::gcd（<numeric> ヘッダ）を使うこともできます。

• s != g のチェックは重要です。s == g の場合、s - g = 0 となり、0は正の整数のペアとして不適切だからです（例：sum = 4、gcd = 4 の場合は -1 を返します）。

• 判定条件 __gcd(g, s - g) == g は、「s - g が g の倍数であること」を確認しています。これにより、2つの数のGCDが本当に g と一致することが保証されます。

• 計算量はGCD計算の O(log(min(a, b))) のみと非常に効率的で、大きな数でも高速に動作します。