一、巴什博奕（Bash Game）
1.游戏规则：
只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。
2.详解:
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)r+s，(r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k(≤m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下(m+1)的倍数，就能最后获胜。
对于巴什博弈，那么我们规定，如果最后取光者输，那么又会如何呢?
当 n % (m+1) = 0时，后手必胜。
当 n % (m+1) != 0时，先手必胜。
注意
1.变形玩法：两个人轮流报数，每次至少1个数，最多报10个数字，谁先报到100取胜。
2.只有一堆n个石子，两个人轮流从这堆石子中取石子，规定每次至少取一个，最多取m个，最后取完的人获胜。
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if(n % (m+1) !=0)
cout<<"first win";
else
cout<<"second win";
return 0;
}二、威佐夫博弈（Wythoff Game）
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
直接说结论了，若两堆物品的初始值为（x，y），且 x < y，则另z=y-x;
记w=(int)[(sqrt(5)+1)/2)*z]；
若w=x，则先手必败，否则先手必胜。
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n1,n2,temp;
while(cin>>n1>>n2)
{
if(n1>n2) swap(n1,n2);
temp=floor((n2-n1)*(1+sqrt(5.0))/2.0); //floor()函数，向下取整
if(temp==n1) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}三、尼姆博弈（Nimm Game）
尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
结论就是：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n,ans,temp;
while(cin>>n)
{
temp=0;
for(int i=0;i<n;i++)
{
cin>>ans;
temp^=ans;
}
if(temp==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}四、斐波那契博弈
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）
#include <iostream>
#include <string>
using namespace std;
const int N = 50; //第47个斐波那契数 2971215073已经超过了整数范围
int f[N];
void Init()
{
f[0] = f[1] = 1;
for(int i=2;i<N;i++)
f[i] = f[i-1] + f[i-2];
}
int main()
{
Init();
int n; //int最大数值是2147483647
while(cin>>n)
{
if(n == 0) break;
bool flag = 0;
for(int i=0;i<N;i++) //所以只需要枚举到N即可
{
if(f[i] == n)
{
flag = 1;
break;
}
}
if(flag) puts("Second win");
else puts("First win");
}
return 0;
} 
