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回ずつ減算を繰り返す素朴な方法では処理に膨大な時間がかかってしまいます。そこで、同じ操作の繰り返しを剰余演算（%）で一括して行うことで、高速に答えを求められます。

C++による実装例

#include<iostream>
using namespace std;

void alterNumber(long long x, long long y) {
    while (true) {
        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

アルゴリズムのポイント

このプログラムの動作は以下の通りです。

1. x または y のどちらかが 0 になった時点でループを抜けます。
2. x ≥ 2y の場合、「x から 2y を繰り返し引く」操作は x % (2y) を代入することと同じ結果になります。
3. y ≥ 2x の場合も同様に、y % (2x) を代入することで複数回の減算をまとめて処理できます。
4. x < 2y かつ y < 2x の状態になると、それ以上値が変化しないためループを終了します。

実行例の流れ（x = 12、y = 5 の場合）

• 12 ≥ 2×5 = 10 なので、x = 12 % 10 = 2 となります。
• 次に 5 ≥ 2×2 = 4 なので、y = 5 % 4 = 1 となります。
• さらに 2 ≥ 2×1 = 2 なので、x = 2 % 2 = 0 となります。
• x が 0 になったため処理を終了し、最終結果は X: 0、Y: 1 です。

このように剰余演算を活用することで、10¹⁸規模の大きな数でも瞬時に最終値を求めることができます。