【题目描述】

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

【输入描述】

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

【输出描述】

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

【样例输入】

2	1

【样例输出】

0

【题目分析】

这道题目描述的是一个经典的博弈论问题，称为威佐夫博弈（Wythoff's Game）。游戏规则如下：

有两堆石子，数量分别为 a 和 b。  两名玩家轮流操作，每次可以选择：   从其中一堆取走任意数量的石子（至少取 1 颗）；   从两堆中同时取走相同数量的石子。  取走最后一颗石子的人获胜。

我们需要判断给定初始状态 (a, b) 时，先手玩家是否有必胜策略。

【例子分析】

输入（1，2），输出0，先手必败

当前玩家无法避免将游戏转移到必胜态：  从第一堆取1个：(0, 2)（对手可从第二堆取2个，直接获胜）；  从第二堆取1个：(1, 1)（对手可同时从两堆取1个，直接获胜）；  从第二堆取2个：(1, 0)（对手可从第一堆取1个，直接获胜）；  从两堆同时取1个：(0, 1)（对手可从第二堆取1个，直接获胜）。  无论怎么操作，对手都能获胜，因此 (1, 2) 是必败态。

输入（3，5），输出0，先手必败

所有可能的操作均导致必胜态：  从第一堆取1个：(2, 5)（对手可转移到 (2, 1) 或 (1, 3) 等必胜策略）；  从第一堆取2个：(1, 5)（对手可转移到 (1, 2) 必败态，但需强制转移）；  从第二堆取2个：(3, 3)（对手可同时取3个直接获胜）；  从两堆同时取3个：(0, 2)（对手可从第二堆取2个直接获胜）。  无论怎么操作，对手都能将游戏转移到必败态或直接获胜。

输入（4，7），输出0，先手必败

所有操作均导致对手必胜：  从第一堆取1个：(3, 7)（对手可转移到 (3, 5) 必败态）；  从第二堆取3个：(4, 4)（对手可同时取4个直接获胜）；  从两堆同时取4个：(0, 3)（对手可从第二堆取3个直接获胜）。

输入（2，1），输出0，先手必败

输入（1，1），输出1，先手必胜

分析：  必败态均为两堆石子数不等（如 (1,2)、(3,5)），因此 (1,1) 是必胜态。  策略：直接取光两堆石子，立即获胜。  步骤：从两堆各取1个，得到 (0, 0)，对手无法操作，先手胜。

输入（2，3），输出1，先手必胜

从两堆各取1个：(2,3) → (1,2)  对手面临 (1,2)（必败态），先手必胜。

输入（4，6），输出1，先手必胜

从两堆各取1个：(4,6) → (3,5)。  对手面临 (3,5)（必败态），先手必胜。

输入（5，8），输出1，先手必胜

从两堆各取1个：(5,8) → (4,7)。  对手面临 (4,7)（必败态），先手必胜。

判断方法

给定 (a, b)（假设 a ≤ b），判断是否为必败态的方法：

1. 计算 $k=b-a$；

2. 计算 $a_{\text{expected}}=\lfloor \varphi \cdot k\rfloor$；

3. 如果 $a=a_{\text{expected}}$，则当前状态是必败态（先手必败），否则先手有必胜策略。

具体步骤如下：

1. 计算 $\varphi =\frac{1+\sqrt{5}}{2}$；

2. 对于输入 (a, b)，假设 a ≤ b，计算 $k=b-a$；

3. 计算 $\text{tmp}=\lfloor k\cdot \varphi \rfloor$；

4. 如果 tmp == a，则当前是必败态，输出 0；否则输出 1。

【参考代码】

#include <bits/stdc++.h>  using namespace std;  int main(){      int a,b;      while(cin>>a>>b){          if(a>b){              swap(a,b);          }          if(a==b){              cout<<1<<endl;          }          if(a==(int)(((sqrt(5)+1)/2*(b-a)))){              cout<<0<<endl;          }          else{              cout<<1<<endl;          }      }      return 0;  }