HDU 1525 Euclid's Game：歐幾里得遊戲的遞歸必勝策略分析

HDU 1525 Euclid's Game：從輾轉相除到博弈必勝態

兩位玩家給定兩正整數 a, b。每回合將較大數減去較小數的任意正整數倍（結果不得為負）。先將任一數減至 0 者獲勝。這是經典的 Euclid's Game，其解法深刻體現了數論與博弈論的結合。

狀態分類與遞歸判定

設 a ≥ b，定義 win(a, b) 為當前玩家是否必勝：

1. a == b：可直接減至 0 → N 點（必勝）。
2. a % b == 0：可一次減至 0 → N 點。
3. a ≥ 2b：當前玩家可控制減至 b 或 a % b，必能選擇移動至 P 點 → N 點。
4. b < a < 2b：唯一合法移動為 (b, a-b)，遞歸判定該狀態。

遞歸/迭代實現邏輯

由於 a, b 嚴格遞減，遞歸深度為 O(log max(a,b))，極為高效。迭代版本更簡潔：

bool stanWin = true; // 先手 Stan
while (true) {
    if (a < b) swap(a, b);
    if (a % b == 0 || a / b >= 2) break; // 當前玩家必勝
    a = a - b; // 唯一移動
    stanWin = !stanWin; // 交換玩家
}
// stanWin 為 true 則先手勝

完整 AC 代碼（C++）

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

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b) == 2) {
        if (a == 0 && b == 0) break;
        bool stan = true;
        while (true) {
            if (a < b) swap(a, b);
            if (a % b == 0 || a / b >= 2) break;
            a -= b;
            stan = !stan;
        }
        printf("%s wins\n", stan ? "Stan" : "Ollie");
    }
    return 0;
}

數學本質：連續分數與黃金分割

本質上，遊戲走勢對應歐幾里得算法的商序列。若某步商 ≥ 2，當前玩家可決定勝負；若所有商均為 1，則對應斐波那契數列，勝負取決於步數奇偶。這與威佐夫遊戲、黃金分割比例有深層聯繫。

拓展思考

• 多堆擴展：Nim 和 Euclid 遊戲的結合。
• 誤差允許：近似比例遊戲的策略改變。
• 三數以上：多維歐幾里得算法的博弈分析。

Euclid's Game 是理解「遞歸博弈」、「不變量」與「數論結構」的絕佳教材，掌握其核心邏輯有助於解決更複雜的組合遊戲問題。