HDU 1525 Euclid's Game：歐幾里得博弈解析

HDU 1525 - Euclid's Game 解題報告

遊戲規則：給定兩個自然數 (a, b)，雙方輪流操作，每次將較大數減去較小數的任意正整數倍（結果不得為負）。先使任一數變為 0 者獲勝。輸入多組 (n, m)，n,m ≤ 10⁹，n=m=0 結束。輸出先手獲勝輸出 "Stan wins"，否則 "Ollie wins"。

核心觀察

這是一個經典的歐幾里得博弈。關鍵在於當較大數 ≥ 2×較小時，先手擁有決定權，必勝；否後雙方被迫唯一操作（減去 1 倍），勝負取決於遞歸深度的奇偶性。

遞歸/迭代判斷邏輯

設 a ≥ b：

• 若 b == 0 或 a % b == 0：當前玩家直接獲勝（可減去恰好倍數使對方面臨 0）。
• 若 a ≥ 2*b：當前玩家可選擇減去 k*b 使剩餘在 [b, 2b) 區間，從而控制勝負，必勝。
• 否則（b < a < 2b）：唯一合法操作是 a → a-b，換手繼續，勝負取反。

參考代碼（C++）

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

int main() {
    long long n, m;
    while (scanf("%lld%lld", &n, &m) == 2 && (n || m)) {
        if (n < m) swap(n, m);
        bool firstWin = true; // true 表示當前玩家（Stan）贏
        while (true) {
            if (m == 0 || n % m == 0 || n >= 2 * m) break;
            n = n - m;
            swap(n, m);
            firstWin = !firstWin;
        }
        puts(firstWin ? "Stan wins" : "Ollie wins");
    }
    return 0;
}

複雜度

每次遞歸至少將較大數減半（類似輾轉相除法），時間 O(log max(n,m))，極快。

關鍵點總結

1. 當 a ≥ 2b 時，先手可通過選擇減去的倍數強制進入必勝態，無需遞歸。
2. 否則遊戲退化為唯一路徑，勝負由步數奇偶決定。
3. 代碼簡潔，利用循環模擬遞歸過程，翻轉標誌位。