HDU 2177 取石子遊戲：威佐夫博弈（Wythoff Game）完整解析與 C++ 實現

題目背景

HDU 2177「取(2堆)石子遊戲」是經典的組合博弈論問題——威佐夫博奕（Wythoff Game）的直接應用。遊戲規則：兩堆石子，雙方輪流操作，每次可從任意一堆取任意多顆，或從兩堆同時取相同數量。取走最後一顆石子者獲勝。給定初始狀態 (a, b)，先手在雙方最優策略下是否必勝？若必勝，第一步該如何取？

威佐夫博弈核心理論

奇異局勢（P-position）

遊戲中存在一系列「必敗局勢」（奇異局勢），記為 (a_k, b_k)，滿足：

• a_0 = b_0 = 0
• a_k 是未在前面出現過的最小自然數
• b_k = a_k + k

前幾個奇異局勢：(0,0), (1,2), (3,5), (4,7), (6,10)...

判斷公式

利用黃金分割比 φ = (1+√5)/2 ≈ 1.618：

a_k = ⌊k * φ⌋
b_k = a_k + k

給定局勢 (a, b) 且 a ≤ b，令 k = b - a。若 a == ⌊k * φ⌋，則為奇異局勢，先手必敗（輸出 0）；否則先手必勝（輸出 1），並需找出一步到達的奇異局勢。

獲勝移動的尋找策略

先手必勝時，需找到一步操作使對手面臨奇異局勢。優先輸出「同時從兩堆取相同數量」的方案。具體判斷邏輯如下：

1. 計算目標奇異局勢 (aa, bb)，其中 aa = ⌊k*φ⌋, bb = aa + k。
2. 若 a - aa == b - bb 且 a > aa，說明可同時取走 a-aa 顆到達該奇異局勢，輸出 aa bb。
3. 否則嘗試僅從一堆取石子：分別以不變的 a 或 b 為基準，反推可能的 k 值，驗證是否能構成奇異局勢，並按題目要求順序輸出。

C++ 參考代碼

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

int main() {
    const double phi = (1.0 + sqrt(5.0)) / 2.0;
    int a, b;
    while (cin >> a >> b, a || b) {
        if (a > b) swap(a, b);
        if (a == 0) { // 先手全取 b 堆獲勝
            cout << "1\n0 0\n";
            continue;
        }
        int k = b - a;
        int aa = (int)(k * phi);
        if (aa == a) { // 面臨奇異局勢，先手必敗
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        int bb = aa + k;
        // 1. 嘗試同時取
        if (a - aa == b - bb && a > aa) {
            cout << aa << ' ' << bb << '\n';
        }
        // 2. 僅取 b 堆，a 不變
        int k2 = (int)(2.0 * a / (1.0 + phi)) + 1;
        int bb2 = a + k2;
        int aa2 = (int)(k2 * phi);
        if (aa2 == a && b > bb2) {
            cout << a << ' ' << bb2 << '\n';
        }
        // 3. 僅取 a 堆，b 不變（將 a 視為奇異局勢的 b）
        int k3 = (int)(2.0 * a / (3.0 + phi)) + 1;
        int bb3 = a;
        int aa3 = (int)(k3 * phi);
        if (bb3 - k3 == aa3) {
            cout << aa3 << ' ' << a << '\n';
        }
        // 4. 僅取 a 堆，b 不變（另一種情況）
        int k4 = (int)(2.0 * b / (3.0 + phi)) + 1;
        int bb4 = b;
        int aa4 = (int)(k4 * phi);
        if (bb4 - k4 == aa4 && aa4 <= a && a != b) {
            cout << aa4 << ' ' << b << '\n';
        }
    }
    return 0;
}

複雜度分析

時間複雜度 O(1) 每測試用例，空間複雜度 O(1)。利用數學公式直接計算，無需 DP 或遞歸，極其高效。