题意

经典的 威佐夫博弈（Wythoff Game）：

• 有两堆石子，数量分别为 $a$ 和 $b$
• 每次可以进行两种操作：

1. 从任意一堆取任意多石子
2. 从两堆中取相同数量的石子

• 最后把石子全部取完的人获胜

要求：判断先手在初始状态下是否能获胜。

解析

威佐夫博弈中，有两种关键状态：

• P-position（必败点）：如果先手处于此状态，必败
• N-position（必胜点）：如果先手处于此状态，必胜

设 $m=\max(a,b)$，$n=\min(a,b)$，则 $(n,m)$ 是 P-position 当且仅当：

$\displaystyle n=\lfloor(m-n)\cdot\phi\rfloor$

其中 $\phi$ 是黄金比例：

$\displaystyle\phi=\frac{1+\sqrt{5}}{2}\approx 1.6180339887$

所有其他状态都是 N-position（先手必胜）。

判定

1. 令 $m=\max(a,b)$，$n=\min(a,b)$；
2. 计算差值 $k=m-n$；
3. 若 $n=\lfloor k\cdot\phi\rfloor$，则输出 0（先手必败）；
4. 否则输出 1（先手必胜）。

证明

已知游戏状态 $(a,b),a\le b$

定义：$P$ 为必败状态，$N$ 为必胜状态

设 $P$ 集合 $(x_n,y_n),x_n<y_n$，差值 $d_n = y_n-x_n$

$\because$ $P$ 不能互相干扰

$\therefore\forall i\ne j,x_i \ne x_j,y_i \ne y_j,d_i \ne d_j$

$\because$ 若 $\alpha>1$ 无理数，$\beta = \frac{\alpha}{\alpha-1}$(Beatty 定理)

$\displaystyle\therefore{\lfloor n\alpha \rfloor}_{n\ge1} \cup {\lfloor n\beta \rfloor}_{n\ge1} = \mathbb{Z}^+,{\lfloor n\alpha \rfloor} \cap {\lfloor n\beta \rfloor} = \emptyset$

令 $\phi = \frac{1+\sqrt{5}}{2}$

$\because$ 黄金比例满足 Beatty 定理

$\therefore x_n = \lfloor n\phi \rfloor,y_n = x_n+n$，差值 $y_n-x_n = n$

$\because$ $x_n$ 序列和 $n$ 构成 Beatty 序列

$\therefore$ 不可能通过一步到达另一个 $P$

设 $N(a,b),a<b,k=b-a$

$\because$ 存在唯一 $n$，$x_n \le a < x_{n+1}$

$\therefore$ 存在一步 $(a,b)\to(x_n,y_n)$

设 $m = \max(a,b),n = \min(a,b),k = m-n$
$\therefore(a,b) \in P \iff n = \lfloor k \phi \rfloor$

$\because$ $P$ 构造 $(x_n,y_n)=(\lfloor n\phi \rfloor,\lfloor n\phi \rfloor+n)$

$\because$ 差值 $k=y_n-x_n=n$

$\therefore$ $x_n = \lfloor k \phi \rfloor$

标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int a,b;
    cin>>a>>b;
    if(a>b)swap(a,b);
    int k=b-a;
    int t=k*16180339887498948482/10000000000000000000;//避免精度误差，使用整型
    cout<<(t==a?0:1)<<endl;
    return 0;
}

后记

复杂度：$\mathcal{O}(1)$。