Bash游戏（同余）：

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。

小学的时候沉迷的游戏…

如果n可以整除k+1的话，B有必胜策略，只要报k+1-A报的数就可以了。

如果不整除的话，由于A先手，所以A就胜了。

Nim游戏（异或）：

有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。

如果把n堆抽象为n个非负整数,再将n个整数转化为二进制,然后对n个二进制数按位相加(不进位),若每一位相加都为偶数,那么称这个状态为偶状态,否则称它为奇状态.

事实一：假设轮到你行动了，这时堆里的Nim和为0。这样不管你怎么做，你动作后的Nim和不会等于0.

事实二：假设轮到你行动了，这时堆里的Nim和不为0。但是可以保证的是，存在一种取法能在你行动后的堆的Nim和为0。

现在如果你是玩家A，所以你先走。接着假设现在堆里的Nim和不等于0.你的策略将会是这样:如果可能尽可能使得下一个Nim和，也就是你动作后的Nim和为0.这也意味着无论B如何动作通过事实1可知，B的这个动作会把下个Nim和变得不为0.

让我们开始，在表中记录每一步的Nim和：

下一个要走的玩家	Nim和	能否变为0？	下个Nim和
A	非0	能	0
B	0	否	非0
A	非0	能	0
B	0	否	非0
A	非0	能	0
……

这个像乒乓球一样的Nim和不断在0和非0之间转化，意味着你保证能赢！如果B注定要赢，她将要把最后一个硬币攒在手中。也就是说：她需要一个动作来产生零Nim和，但在我们看来这是不可能的。你的每次动作，都在把Nim和减少到0。当游戏进行到快到结尾时时，零Nim和就等价于没有一个硬币剩余——这时你就赢了。

那么对于n堆物品,只要判断它是否是奇状态就可以判断是否先手有必赢策略.

以非零Nim和打头的游戏，玩家A都有一个必胜策略。策略就是在每一步都让下一个Nim和减少到0.

如果游戏开始时为零Nim和，那么玩家B有一个必胜策略。当轮到B动作时不管玩家A在第一步做了什么将会留下一个非零Nim和。那么按同上的理由，必胜策略掌握在了B的手中。

但是求每个数的二进制表示略显麻烦,可以用位运算.

XOR 和判断: 如果有奇数个二进制数在第K位为1 那么在这一位上的和为奇,同样的，偶数个1和为偶.

很明显位运算xor满足我们的要求,偶数个1异或和为0,奇数个为1。

当这些数都做异或运算时等于0时,先手输，否则后手输。

如果Nim游戏中的规则稍微变动一下,每次最多只能取K个,怎么处理?

方法是将每堆石子数mod (k+1).

int main()
{
    int t,n,k,sum=0,ch;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&ch);
        sum=sum^ch;
    }
    if(sum==0)printf("B\n");
    else printf("A\n");
    return 0;
}

反Nim游戏：

在反尼姆博奕中判断必胜局面的条件有两点，满足任意一点先手都能取胜，即必胜局面。

1：各堆石子数目异或结果不等于0，且存在有石子数目大于1的石子堆。

2：各堆石子数目异或结果等于0，且所有石子堆数目全部为1。

Wythoff游戏（黄金分割）：

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,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）。

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k。

若两堆物品的初始值为（x，y），且x<y，则另z=y-x；记w=（int）[((sqrt(5)+1)/2）*z ]；若w=x，则先手必败，否则先手必胜。

给你一个局面，让你求先手输赢，假设先手赢的话输出他第一次的取法。

​ 首先讨论在两边同时取的情况，很明显两边同时取的话，不论怎样取他的差值是不会变的，那么我们可以根据差值计算出其中的小的值，然后加上差值就是大的一个值，当

然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。

​ 加入在一堆中取的话，可以取任意一堆，那么其差值也是不定的，但是我们可以枚举差值，差值范围是0 —- 大的石子数目，然后根据上面的理论判断满足条件的话就是一种合理的取法。

int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        if(a==0&&b==0)break;
        if(a>b)swap(a,b);
        int d=b-a;
        int x=(int)((sqrt(5)+1)/2*d);//这里注意！
        if(x==a)printf("0\n");
        else
        {
            printf("1\n");
            int ans1,ans2;
            if(a>x)
            {
                ans1=x;
                ans2=b-a+x;
                printf("%d %d\n",ans1,ans2);
            }
            for(int i=1;i<=b;i++)
            {
                ans1=a;ans2=b-i;
                if(ans1>ans2)swap(ans1,ans2);
                d=ans2-ans1;
                x=(int)((sqrt(5)+1)/2*d);
                if(x==ans1)
                    printf("%d %d\n",ans1,ans2);
            }
            if(a!=b)//如果a和b相同的话在a堆取和在b堆取是一样的
            {
                for(int i=1;i<=a;i++)
                {
                    ans1=a-i;ans2=b;
                    if(ans1>ans2)swap(ans1,ans2);
                    d=ans2-ans1;
                    x=(int)((sqrt(5)+1)/2*d);
                    if(x==ans1)
                        printf("%d %d\n",ans1,ans2);
                }
            }
        }
    }
    return 0;
}

斐波那契博弈（找规律）：

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜。

n = 2时输出second；
n = 3时也是输出second；
n = 4时，第一个人想获胜就必须先拿1个，这时剩余的石子数为3，此时无论第二个人如何取，第一个人都能赢，输出first；
n = 5时，first不可能获胜，因为他取2时，second直接取掉剩下的3个就会获胜，当他取1时，这样就变成了n为4的情形，所以输出的是second；
n = 6时，first只要去掉1个，就可以让局势变成n为5的情形，所以输出的是first； n = 7时，first取掉2个，局势变成n为5的情形，故first赢，所以输出的是first；
n = 8时，当first取1的时候，局势变为7的情形，第二个人可赢，first取2的时候，局势变成n为6得到情形，也是第二个人赢，取3的时候，second直接取掉剩下的5个，所以n = 8时，输出的是second；
…………
从上面的分析可以看出，n为2、3、5、8时，这些都是输出second，即必败点，仔细的人会发现这些满足斐波那契数的规律，可以推断13也是一个必败点。
借助“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。n=12时，只要谁能使石子剩下8且此次取子没超过3就能获胜。因此可以把12看成8+4，把8看成一个站，等价与对4进行”气喘操作”。又如13，13=8+5，5本来就是必败态，得出13也是必败态。也就是说，只要是斐波那契数，都是必败点。

先手胜当且仅当n不是斐波那契数（n为物品总数）