HDU 1527 取石子遊戲：威佐夫博弈數學解法

問題描述

兩堆石子，雙方輪流取。每次可：任意一堆取任意多，或兩堆同時取相同數量。取完者勝。給定初始數目 (a,b)，先手在雙方最優策略下勝負判斷。

威佐夫博弈理論

局勢表示為 (ak, bk)（ak ≤ bk）。(0,0) 為奇異局勢（先手必敗）。前幾個奇異局勢：

(0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)

規律：a0=b0=0，ak 為未出現過的最小自然數，bk = ak + k。

若雙方最優操作，面對非奇異局勢先手必勝，奇異局勢先手必敗。

判斷算法

int k = abs(u - v);
int n = (int)(k * (1 + sqrt(5)) / 2.0);  // 黃金分割點
if (n == min(u,v)) 是奇異局勢（先手敗）；
else 先手勝。

AC 代碼

#include 
#include 
using namespace std;

int main() {
    int u, v;
    while (cin >> u >> v) {
        int k = abs(u - v);
        int n = (int)(k * (1 + sqrt(5)) / 2.0);
        if (n == min(u, v)) cout << "0\n";
        else cout << "1\n";
    }
    return 0;
}

時間複雜度 O(1)，完美解決 a,b ≤ 1e9 的大數據範圍。