$\rm{Description}$

有两堆，若干个物品，两个人轮流从某一堆或从两堆中取同样多的物品，规定每次最少拿走一个，最多不限制，最后拿光的人获胜。

$\rm{Analysis}$

用A表示先手玩家，B表示后手玩家，当前是A进行操作。为了判断 A 是否有必胜策略，可以这样分析：

• 用有序数对 $(a, b)$ 表示两堆物品的数量状态；
• $(0, 0)$ 是 $A$ 的必败策略，因为此时 $A$ 已输；
• 若局面能够移动到 $B$ 无必胜策略的局面，那么这个局面是 $A$ 的必胜态；
• 若局面无论怎么移动，都会变成 $B$ 的必胜太，那么这个局面是 $A$ 的必败态。

通过枚举，可以发现 $A$ 的必败态有：

用有序数对序列$(a_0, b_0),(a_1, b_1),(a_2, b_2)\ldots$表示上面的必败态，可以看出，满足：$a_0=b_0=0$ 且 $b_i=a_i+i$，$a_i$ 是之前没有出现过的最小自然数。

$\rm{Demonstrate}$

前置命题： $a_{n+1}$ 是前 $n$ 组必败态中没有出现过的最小正整数。

证明命题： $\forall n, b_n=a_n+n$.

考虑归纳证明。若前 $k$ 个必败态分别为 $(a_1, a_1+1), (a_2, a_2+2), \cdots, (a_k, a_k+k)$，下证：第 $k+1$ 个必败态为 $(a_{k+1}, a_{k+1}+k+1)$.

从这个必败态出发，一共可能走向三类状态：从第一堆拿走，从第二堆拿走，或者两堆同时拿走，只需证明这三类都是必胜态。

情况一：从第一堆拿走一些。

因为任意一个比 $a_{k+1}$ 小的数都在之前的必胜态中出现过，第一堆变少之后，只需要把第二堆拿到第一堆对应的必败态。所以对于出现的新的状态，都可以直接指向必败态。

情况二：从第二堆拿走一些。

1. 拿完之后第二堆仍然大于第一堆。此时可以表示成 $(a_{k+1}, a_{k+1}+m), (m
   
2. 拿完之后第二堆小于第一堆，设其拿成了 $(a_{k+1}, m)$，则 $m
   

情况三：两堆同时拿走一些。

设拿完之后的状态是 $(m, m+k+1)$。因为 $m

所以现在已经得到了数列关系式 $b_n=a_n+n$.

$\rm{Attribute}$

在这个问题中，我们称必败态为奇异局势，记为 $(a_k, b_k)$ 那么有如下性质：

1. 任何自然数都包含在一个且仅一个奇异局势中

因为 $a_k$ 是之前没有出现过最小自然数，所以所有自然数都会被包含到奇异局势当中。

由于 $a_k>a_{k-1}$，所以 $b_k=a_k+k>a_{k-1}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$。整理后，有 $b_k > b_{k-1}>a_{k-1}$，所以不存在自然数被两个奇异局势包含。

2. 任意操作都可以将奇异局势变为非奇异局势

也就是说，必败态的后继一定都是必胜态。

对于奇异局势 $(a_k, b_k)$，如果只改变其中一个数，那么由性质$1$，不可能是另一个奇异局势；

如果同时改变两个数，那么这两个数的差不变，由于 $b_k=a_k+k$，对于一个差值，只可能对应一个奇异局势，所以变化后也不可能是另一个奇异局势。

3. 可以将非奇异局势变为奇异局势

根据奇异局势满足 $b_k=a_k+k$，可以分类讨论进行证明。

具体地，对于任意的局势 $(a, b)$，

若 $a=b$，那么同时取走 $a$ 个物品即可变为 $(0, 0)$；

若 $a$ 是一个奇异局势中的 $a_k$，且 $b>b_k$，那么从 $b$ 堆中取出 $b-b_k$个物品，变为 $(a_k, b_k)$.

若 $a$ 是一个奇异局势中的 $a_k$，且 $b

若 $a$ 不属于任何一个奇异局势中，那么 $b$ 一定是一个奇异局势中的 $b_k=a_k+k$，此时有两种情况：

如果 $a>a_k$，从第一堆中拿走多余的 $a-a_k$.

如果 $a

$\rm{Conclusion}$

快速判断局势 $(a, b)$ 是否是奇异局势的方法。

Beatty定理

设 $a, b$ 是正无理数，且 $\frac{1}{a}+\frac{1}{b}=1$，记 $P=\lfloor{na}\rfloor, Q=\lfloor{nb}\rfloor$，$n$ 为任意正整数。

那么 $P\cap Q=\emptyset$ 且 $P\cup Q=N^{*}$.

也就是说：取两个正无理数 $\frac{1}{\alpha}+\frac{1}{\beta}=1$，构造两个数列 $a_n=\lfloor\alpha n\rfloor$ 和 $b_n=\lfloor\beta n\rfloor$，那么两个数列单调递增，并且每个正整数在两个数列当中出现且仅出现一次。

推导

发现奇异局势和 Beatty 定理的条件很像，考虑计算出 $\alpha$ 和 $\beta$.

两个数列 $a_n$ 和 $b_n$ 就是奇异局势中的 $(a_n, b_n)$.

$a_n+n=\lfloor{\alpha\cdot n}\rfloor+n=\lfloor{(\alpha+1)\cdot n}\rfloor=\lfloor{\beta\cdot n}\rfloor$.

所以 $\alpha+1=\beta$

所以 $\frac{1}{\alpha}+\frac{1}{\beta}=\frac{1}{\alpha}+\frac{1}{\alpha+1}=1$.

解得 $\alpha=\frac{\sqrt{5}+1}{2}$.

所以 $a_n=\lfloor\frac{\sqrt{5}+1}{2}n\rfloor$，$b_n=\lfloor(\frac{\sqrt{5}+1}{2}+1)n\rfloor=\lfloor\frac{3+\sqrt{5}}{2}n\rfloor=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

所以根据 Beatty 定理，奇异局势的通项公式为：$a_n=\lfloor(\frac{\sqrt{5}+1}{2})n\rfloor$，$b_n=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

而 $\frac{\sqrt{5}+1}{2}$ 是黄金比，所以威佐夫博弈的奇异局势与黄金比相关。

判断方法

根据奇异局势的性质，对于需要判断的局势 $(a, b), (a

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
bool eq(double a, double b) {
	if(abs(a - b) < 1e-4) return true;
	else return false;
}
int main() {
	double a, b; cin >> a >> b;
	if(a > b) swap(a, b);
	double t = (1.0 + sqrt(5.0)) / 2.0;
	double k = b - a;
	if(eq(floor(k * t), a) && eq(floor(k * t * t), b)) {
		cout << 0 << endl;
	} else {
		cout << 1 << endl;
	}
	return 0;
}