POJ 1067 取石子游戏（威佐夫博弈）

题目链接：
POJ 1067 取石子游戏
题意：
有两堆石子各有$a,b$个，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。判断先手是胜者还是负者。
数据范围;$a,b\leq 10^9$
分析；
威佐夫博弈（Wythoff Game）。
我们用 $(a_k,b_k),a_k\leq b_k,k=0,1,2,…,n$ 表示两堆物品的数量并称其为局势，如果甲面对$(0，0)$，那么甲已经输了， 这种局势我们称为奇异局势。前几个奇异局势是：$(0,0)$,$(1,2)$,$(3,5)$$(4,7)$,$(6,10)$,$(8,13)$,$(9,15)$,$(11,18)$,$(12,20)$。
可以看出,$a_0=b_0=0$，$a_k$ 是未在前面出现过的最小自然数，而$b_k=a_k+k$，奇异局势有如下三条性质：

• 任何自然数都包含在一个且仅有一个奇异局势中。由于$a_k$ 是未在前面出现过的最小自然数，所以有$a_k>a_{k?1}$，而 $b_k=a_k+k>a_{k?1}+k?1=b_{k?1}>a_{k?1}$。 所以性质1成立。
• 任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势$(a_k,b_k)$的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。 如果使$(a_k,b_k)$的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
• 采用适当的方法，可以将非奇异局势变为奇异局势。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
任给一个局势 $(a,b)$，判断它是不是奇异局势，有如下公式：

$$a_k=\lfloor k\times \frac{1+\sqrt{5}}{2}\rfloor(向下取整),b_k=a_k+k\quad (k=0,1,2,…,n)$$
由于 $\frac{1+\sqrt{5}}{2}=\frac{2}{\sqrt{5} - 1}$，可以先求出 $j=\lfloor a\times \frac{\sqrt{5}-1}{2}\rfloor$，则 $a_j=\lfloor j \times \frac{\sqrt{5}+1}{2}\rfloor$，

• 若$a=\lfloor j \times \frac{\sqrt{5}+1}{2}\rfloor=a_j$那么 判断$b是否等于b_j=a_j+j=a+j$
• 若$a$不等于$a_j$,那么判断是否满足$a=a_{j+1}=\lfloor (j+1) \times \frac{\sqrt{5}+1}{2}\rfloor$,$b=b_{j+1}=a_{j+1}+j+1$
• 若都不是，那么就不是奇异局势。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;int main()
{int a, b;double p = (sqrt(5.0) + 1.0) / 2.0;while(~scanf("%d%d", &a, &b)) {if(a > b) swap(a, b);int k = (int)(a / p);if((a == (int)(k * p) && b == a + k) || (a == (int)((k + 1) * p) && b == a + k + 1)) {printf("0\n");} else {printf("1\n");}}return 0;
}