博弈論（巴什博奕，威佐夫博弈，尼姆博弈，斐波那契博弈）

一、巴什博弈（Bash Game）

有n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m個，最後取光者得勝。

顯然，如果n=m+1，那麼由於一次最多只能取m個，所以，無論先取者拿走多少個，後取者都能夠一次拿走剩餘的物品，後取者取勝。因此我們發現瞭如何取勝的法則：

如果n=（m+1）*k+c，（c為任意自然數，c≤m)，那麼先取者要拿走c個物品，如果後取者拿走x個（x≤m)，那麼先取者再拿走m+1-x個，結果剩下（m+1）（k-1）個，以後保持這樣的取法，那麼先取者肯定獲勝。總之，要保持給對手留下（m+1）的倍數，就能最後獲勝。

所以我們可以知道，如果c=0，即滿足n%（m+1）=0，則後手必勝，否則先手必勝。

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n%(m+1)==0)
        cout<<"later win"<<endl;
        else cout<<"earlier win"<<endl;    
    }
    return 0;
}

假如我們規定最後取光者輸，那麼結果又會如何呢？

如若滿足（n-1）%（m+1）=0，則後手必勝，否則先手必勝。

所以可見其結果並不是簡單的相反而已。

二、威佐夫博弈（Wythoff Game）

有兩堆若幹數量的物品，兩人輪流從其中一堆取至少一件物品，至多不限，或從兩堆中同時取相同件物品，規定最後取完者勝利。

直接說結論了，若兩堆物品的初始值分別為n和m，且n>m。

若滿足（int）[（（sqrt（5）+1）/2）*（n-m）]=m，則後手必勝，否則先手必勝。

【tip：左式需先取整！！】

#include <cstdio>  
#include <cmath>  
#include <iostream>  
using namespace std;  
int main()  
{  
    int n,m;
    while(cin>>n>>m)  
    {  
        if(m>n)
        swap(n,m);  
        if(floor((n-m)*(1+sqrt(5.0))/2.0)==m) 
        cout<<"later win"<<endl;  
        else cout<<"earlier win"<<endl;  
    }  
    return 0; 
}