题意分析

题目背景

本题属于组合数学中的博弈论问题，具体为**威佐夫博弈（Wythoff's Game）**的经典模型。游戏规则如下：

1. 初始状态：两堆石子，数量分别为$a$和$b$。
2. 操作规则：
   • 从一堆中取任意数量的石子（至少取1个）。
   • 从两堆中同时取相同数量的石子。
3. 胜负判定：取走最后一颗石子的玩家获胜。
4. 目标：给定初始状态$(a, b)$，判断先手玩家是否有必胜策略（双方均采取最优策略）。

输入输出

• 输入：多组测试数据，每组包含两个整数$a$和$b$（石子数量）。
• 输出：若先手必胜输出1，否则输出0。

解题思路

1. 威佐夫博弈的核心理论

• 必败态（P-position）：当前玩家无法通过任何操作获胜的状态。
• 必胜态（N-position）：当前玩家可以通过至少一个操作将游戏转移到必败态。
• 威佐夫必败态的数学特性： 设$a \leq b$，必败态满足：$$a = \lfloor k \cdot \phi \rfloor, \quad b = a + k$$ 其中：
  • $\phi = \frac{1 + \sqrt{5}}{2}$（黄金比例）。
  • $k$为非负整数。

2. 判断是否为必败态

1. 计算差值：$k = b - a$。
2. 验证条件：
   • 检查$a$是否等于$\lfloor k \cdot \phi \rfloor$。
   • 若成立，则$(a, b)$为必败态，先手必败（输出0）。
   • 否则，先手必胜（输出1）。

3. 数学推导

• 黄金比例的性质： $\phi^2 = \phi + 1$，因此$b = \lfloor k \cdot \phi^2 \rfloor = \lfloor k \cdot (\phi + 1) \rfloor = a + k$。
• 关键不等式： $\phi \cdot k$的小数部分决定了$\lfloor \phi \cdot k \rfloor$的取值。

算法实现

代码框架

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

const double phi = (1.0 + sqrt(5.0)) / 2.0;

int main() {
    int a, b;
    while (cin >> a >> b) {
        if (a > b) swap(a, b);
        int k = b - a;
        int expected_a = (int)(k * phi);
        if (a == expected_a) {
            cout << 0 << endl;
        } else {
            cout << 1 << endl;
        }
    }
    return 0;
}

关键步骤

1. 输入处理：读取每组数据$(a, b)$，并确保$a \leq b$。
2. 计算差值：$k = b - a$。
3. 验证必败态：
   • 计算$\lfloor k \cdot \phi \rfloor$。
   • 比较$a$与计算值，输出结果。

复杂度分析

• 时间：$O(1)$，每组数据仅需常数时间计算。
• 空间：$O(1)$，仅存储常数个变量。