C++で指定した条件に基づいて変化させたときの最終的なXとYの値を求める方法

2つの正の整数 X と Y の初期値が与えられているとします。以下の手順に従って値を変化させていったとき、最終的に残る X と Y の値を求めるのが本記事のテーマです。

処理のルール

• ステップ1：X = 0 かつ Y = 0 の場合は処理を終了します。それ以外の場合はステップ2へ進みます。
• ステップ2：X >= 2Y が成立する場合は X = X − 2Y としてステップ1へ戻ります。成立しない場合はステップ3へ進みます。
• ステップ3：Y >= 2X が成立する場合は Y = Y − 2X としてステップ1へ戻ります。どちらの条件も成立しない場合は処理を終了します。

効率化のポイント

X と Y は最大 10¹⁸ という非常に大きな値を取りうるため、減算を1回ずつ繰り返す単純な総当たり（ブルートフォース）では計算時間が膨大になり、現実的ではありません。

そこで注目するのが、「同じ条件が連続して成立する間は減算が何度も繰り返される」という性質です。例えば X >= 2Y の間、X から 2Y を引き続ける操作は、剰余演算を使った「X = X % (2Y)」と完全に等価になります。これにより、巨大な値でもわずか数ステップで最終値まで到達できます。

C++による実装例

#include<iostream>
using namespace std;

void alterNumber(long long x, long long y) {
    while (1) {
        if (x == 0 || y == 0)
            break;
        if (x >= 2 * y)
            x = x % (2 * y);
        else if (y >= 2 * x)
            y = y % (2 * x);
        else
            break;
    }
    cout << "X: " << x << "\n" << "Y: " << y;
}

int main() {
    long long x = 12, y = 5;
    alterNumber(x, y);
}

出力結果

X: 0
Y: 1

コードの解説

alterNumber 関数は、無限ループの中で3つの条件を順に判定します。

• X または Y が 0 になった時点でループを抜けます。
• X >= 2Y の場合は、減算の繰り返しを剰余演算 x % (2Y) で一括処理します。
• Y >= 2X の場合も同様に、y % (2X) で一括処理します。
• どちらの条件も満たさない場合は、それ以上変化が起こらないため終了します。

入力例 x = 12、y = 5 の場合の流れを追ってみましょう。

1. 12 >= 2×5 が成立するため、x = 12 % 10 = 2 となります。
2. 次に 5 >= 2×2 が成立するため、y = 5 % 4 = 1 となります。
3. 続いて 2 >= 2×1 が成立するため、x = 2 % 2 = 0 となります。
4. x が 0 になったためループを終了し、「X: 0、Y: 1」が出力されます。

このように剰余演算を活用することで、10¹⁸ オーダーの巨大な入力に対しても高速に最終的な X と Y の値を求められる点が、このアルゴリズムの大きな強みです。