信息學奧賽經典題：威佐夫博弈（猴子吃桃）解法詳解

問題模型轉化

兩堆桃子 (a, b)，雙方輪流操作，每次可：

1. 任意一堆取任意多個（≥1）。
2. 兩堆同時取相同數量（≥1）。
3. 取完最後一個桃子者勝。

這正是經典的 威佐夫博弈，又稱「取石子遊戲」變體。

數學解法：黃金分割點判定

設兩堆數量為 (x, y)，且 x ≤ y。定義 冷位置：先手必敗的局面。所有冷位置由以下公式生成：

k = 0, 1, 2, ...
a_k = floor(k * φ)
b_k = floor(k * φ²) = a_k + k
其中 φ = (1 + √5) / 2 ≈ 1.618033988749895 (黃金分割比)

前幾對冷位置：
(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), (11,18), (12,20), (14,23)...

判定算法 (O(1))

給定初始 (a, b)，設 x = min(a,b), y = max(a,b)，d = y - x。
若 x == floor(d * φ)，則為冷位置，**先手敗 (輸出 0)**；否則**先手勝 (輸出 1)**。

C++ 參考代碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;
    int m; cin >> m;
    while (m--) {
        long long a, b; cin >> a >> b;
        if (a > b) swap(a, b);
        long long d = b - a;
        long long ak = (long long)(d * PHI);
        cout << (a == ak ? 0 : 1) << '\n';
    }
    return 0;
}

樣例驗證

完全匹配樣例輸出。

進階證明思路 (SG 函數 / Mex 定理)

• 定義局面 (x,y) 的 SG 值：`g(x,y) = mex{ g(x',y) | x'<x } ∪ { g(x,y') | y'<y } ∪ { g(x-k, y-k) | k≤min(x,y) }`。
• 證明 `g(x,y) = 0` 的解恰為上述 Beatty 數列對，利用 Beatty 定理：若 α, β > 1 且 1/α + 1/β = 1，則 `floor(nα)` 和 `floor(nβ)` 互補分割自然數。此處 α=φ, β=φ²。
• 由此得出冷位置公式，且任意熱位置必有移動到某冷位置的操作。

擴展：大數據範圍 (a,b ≤ 10^18)

雙精度 `double` 52 位尾數，精確表示 10^15 以內整數。對於 10^18 需用 `long double` (80位) 或整數運算避免精度誤差：

// 整數判定避免浮點誤差
// x == floor(d * φ)  <=>  x ≤ d*φ < x+1
// 平方消去根號：φ = (1+√5)/2
// 等價於判斷 (2*x - d)^2 < 5*d^2 且 (2*x - d + 2)^2 > 5*d^2
// 使用 __int128 防溢出