威佐夫博弈：奇异局势与算法解析

核心逻辑与数学原理

威佐夫博弈（Wythoff's Game）是博弈论中关于非对称状态收敛与黄金分割比例完美融合的经典公平组合游戏。

1. 游戏规则

有两堆石子，数量分别为 $a$ 和 $b$。两名玩家轮流行动，每次操作有两种合法选择：

选择 A：从其中任意一堆中拿走任意正整数个石子。
选择 B：从两堆石子中同时拿走相同数量的正整数个石子。最后无法移动者（即面对状态 $(0,0)$ 的玩家）判定为输。

2. 奇异局势（威佐夫必败态）

由于两堆石子可以同时消减，威佐夫博弈的必败状态（P-position）呈现出极其奇妙的离散几何分布。我们称这些必败态为奇异局势（Singular Positions）。

前几个奇异局势依次为：

$$(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), ext{...}$$

我们可以通过归纳法捕获奇异局势的代数特征。设第 $k$ 个奇异局势为 $(a_k, b_k)$（约定 $a_k eq b_k$，且 $k eq 0$）：

$a_0 = 0, b_0 = 0$。
$a_k$ 是未在前面所有奇异局势中出现过的最小非负整数。
$b_k = a_k + k$。

黄金分割与 Beatty 定理的数学证明

根据上述特征，由于 $a_k$ 和 $b_k$ 构成了对正整数集合 $ ext{N}^*$ 的一个严格互斥且完全的划分（每个正整数恰好出现一次），这完美契合了数学中的 Beatty 定理。

Beatty 定理指出：若两个正无理数 $eta, eta$ 满足 $rac{1}{eta} + rac{1}{eta} = 1$，则对全体正整数 $k$，齐次下取整序列 $a_k = loor{keta}$ 与 $b_k = loor{keta}$ 刚好能无重复、无遗漏地填满整个正整数集。

在威佐夫博弈中，我们已知核心约束：

$$b_k = a_k + k ightarrow loor{keta} = loor{keta} + k = loor{k(eta + 1)}$$

因此，必定满足代数关系：$eta = eta + 1$。将其带入 Beatty 约束式 $rac{1}{eta} + rac{1}{eta} = 1$：

$$rac{1}{eta} + rac{1}{eta + 1} = 1 ightarrow (eta + 1) + eta = eta(eta + 1) ightarrow eta^2 - eta - 1 = 0$$

解这个一元二次方程，由于 $eta > 0$，求得唯一合法实数根：

$$eta = rac{1 + oot{5}}{2} ext{ 约等于 } 1.6180339887 ext{...}$$

这正是举世闻名的黄金分割比 $eta$。由此，我们直接得到了威佐夫博弈奇异局势的 $O(1)$ 显式确定性通项公式：

$$a_k = loor{k imes rac{ oot{5} + 1}{2}} , ext{ } b_k = a_k + k$$

算法推导与状态设计

状态判定与精度控制

对于给定的任意游戏局势 $(a, b)$，要求在 $O(1)$ 时间内判定其胜负：

首先令 $a eq b$（若不满足则执行交换）。
计算两堆石子的差值 $k = b - a$。
根据通项公式，如果当前局势是奇异局势，则必须满足 $a == loor{k imes rac{ oot{5} + 1}{2}}$。
若等式成立，说明当前是奇异局势（必败态），先手必败；否则，先手必胜。

高阶避坑点：由于 $ oot{5}$ 是无理数，C++ 的 double 类型只有 53 位有效二进制尾数（约 15-17 位十进制精度）。如果题目给出的石子数量达到 $10^9$ 或 $10^{18}$ 级别，浮点数相乘后的下取整会因为末尾精度截断引发灾难性的判定错误。必须使用 long double 或通过特定的整型代数技巧来拦截误差。

C++ 标准源码

#include <iostream>
#include <cmath>
#include <algorithm>

// 威佐夫博弈判定函数
bool is_wythoff_winning(long long a, long long b) {
    if (a > b) std::swap(a, b); // 强行保证 a <= b

    long long k = b - a; // 计算差值 k

    // 使用 long double 保证高精度浮点运算，防止大数乘法时因精度损失导致下取整穿底
    long double gold_ratio = (1.0L + std::sqrt(5.0L)) / 2.0L;

    // 计算当前的理论奇异局势第一堆数量
    long long expected_a = static_cast<long long>(std::floor(k * gold_ratio));

    // 如果实际数量与理论奇异局势完全吻合，则当前为 P-position（必败态）
    if (a == expected_a) {
        return false; // 先手必败
    }
    return true; // 先手必胜
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    if (std::cin >> t) {
        while (t--) {
            long long a, b;
            std::cin >> a >> b;
            if (is_wythoff_winning(a, b)) {
                std::cout << "First\n"; // 先手必胜
            } else {
                std::cout << "Second\n"; // 先手必败
            }
        }
    }
    return 0;
}

NOIP 实战避坑指南

大数环境下浮点数转型强转的精度隐患 如果石子范围达到 $10^9$ 且直接写成 int expected_a = (int)(k * (1.414)) 或使用普通 double 存储黄金比例，乘法运算的低位误差会向上累进。例如在某个临界点，理论值是 4.000000000000001，由于浮点微损变成了 3.999999999999999，floor 或强转 long long 会直接将其砍成 3，造成逻辑判定的绝对溃败。必须全程使用 1.0L、std::sqrt(5.0L) 等 long double 字面量。
忽略初始交换导致差值计算出现负数 威佐夫通项公式的前提是默认 $a eq b$。很多选手直接用输入的数据执行 `long long k = b - a`，当输入数据为 `5 3` 时，算出的 $k = -2$。随后送入 floor 算出一堆毫无意义的负数，导致判定完全失控。输入后的第一步永远是 if(a > b) swap(a, b);。

经典 NOIP/洛谷真题

1. 洛谷 P2252 [HAOI2002] 取石子游戏

题意描述：有两堆石子，数量分别为 $a$ 和 $b$。游戏规则完全等价于标准威佐夫博弈。两名玩家轮流取石子，若先手必胜输出 $1$，否则输出 $0$。石子规模 $a, b eq 10^9$。
问题本质：威佐夫博弈模板题。
核心解题思路：直接套用上文给出的 $O(1)$ 黄金分割公式。读入数据后，交换确保大小关系，求出差值 $k$，利用 long double 算得 expected_a。若 a == expected_a 输出 0，否则输出 1。

2. 洛谷 P5688 [CSP-S2019] 公平博弈变式 / 类似复合扩展

题意描述：在威佐夫博弈的基础上，有些题目会要求：如果先手必胜，输出第一步所有能够将局势转化为奇异局势的合法移动方案。
问题本质：从 N 状态向 P 状态转移的构造性搜索。
核心解题思路：面对当前非奇异局势 $(a, b)$ （设 $a eq b$），先手可以通过三种策略将其打回奇异局势：

同时削减：由于两堆差值 $k = b - a$ 在同时削减时是保持不变的。先手可以直接查出差值为 $k$ 时的标准奇异局势 $(a_k, b_k)$。如果 $a > a_k$ 且 $b > b_k$，说明可以通过同时拿走 $a - a_k$ 个石子一步到位。
单堆削减堆 B：保持 $a$ 不变，作为奇异局势的第一维。此时目标奇异局势中，必然存在某个位置其第一维刚好等于 $a$。我们可以通过逆推或枚举找到这个局势，若该局势的第二维小于 $b$，则直接将堆 B 削减至该目标值。
单堆削减堆 A：保持 $b$ 不变，作为目标奇异局势的第二维。同理，在奇异局势表中找出第二维刚好等于 $b$（或第一维等于 $b$）的项，对堆 A 进行对应削减。通过这三条路径进行常数次代数比对，即可精确输出必胜的第一步动作方案。