POJ 1067 取石子游戏

两种常见的取物品游戏：
1.一堆物品
两人轮流取一堆物品，物品数量为n,规定每次至少取一个物品，最多为m个，最后取完者获胜。

思路：如果n=m+1,由于一次最多只能取m个物品，那么无论先取者如何去取，后取的都能获胜。
那么先取者想要获胜的关键就是保证每次取完之后剩余物品的数量都是m+1的倍数，即如果n=r(m+1)+s，先取者要先取走s个，依次保持下去。

2.两堆物品
经典的例子就是POJ ACM 1067题，两个人轮流取石子，每人可以从一堆中取任意数量的石子，或者从两堆中取走相同数量的石子，给定两堆石子的食量，问先取者是否可以获胜。

威佐夫博弈：用(ak,bk)表示两堆物品数量，称之为局势，如果甲面对(0,0)局势，那么说明甲已经输了，类似的局势还有
(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)...
这种局势叫做奇异局势,ak是前面没有出现的最小自然数，bk=ak+k
奇异局势的特点：
1.任何一个自然数都包含在一个且仅有一个奇异局势中。
2.任何操作都可以将奇异局势变为非奇异局势。
3.可以通过适当的方法将非奇异局势变为奇异局势。
所以面对奇异局势的人是不能获胜的。

判断一个局势是不是奇异局势的方法：
ak=[k(1+√5)/2],bk=ak+k  ([]是取整运算)

(1+√5)/2=1.6180339887...黄金分割数
于是，取石子游戏的实现如下：

#include<stdio.h>
int main()
{
    int n,m,k;
    double R=1.6180339887,r=1/R;
    scanf("%d%d",&n,&m);//input
    //swap if n>m
    if(n>m)
    {
        k=n;
        n=m;
        m=k;
    }
    k=n*r;
    if(n!=(int)k*R)
        ++k;
    if(m!=(int)k*R+k)
      printf("1\n");
    else
      printf("0\n");
}