SG函数先不说，给自己总结下三大博弈。和二进制及黄金分割联系密切，数学真奇妙，如果不用考试就更好了。

1.Bash Game：n个物品，最少取1个，最多取m个，先取完者胜。

给对手留下(m+1)的倍数肯定获胜。若n%(m+1)==0，先手必败。

51nod裸题：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int main(){ 5     int t; cin>>t; 6     int n,k; 7     while(t--){ 8         cin>>n>>k; 9         if(n%(k+1)==0)  puts("B");10         else  puts("A");11     }12     return 0;13 }
      
     

 

 

2.Nim Game：n堆物品，取某一堆的若干个，至少取一个，多者不限，先取完者胜。

在这个博弈中，对任何奇异局势 (a,b,c....n)，都有a^b^...^n==0。

所以直接检测给的局势，若是奇异局，先手必败。

如何将(a,b,c)转化成奇异局：将c变为a^b,即c -= a^b（^是异或）

51nod裸题：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int main(){ 5     int a[1005]={
   0}; 6     int ans=0; 7     int n; cin>>n; 8     for(int i=0;i
       
        >a[i];10         ans^=a[i];11     }12     if(ans)  puts("A");13     else  puts("B");14     return 0;15 }
       
      
     

 

 

3.Wythoff's Game：两堆若干个，轮流从某一堆取任意个或同时从两堆取同样多任意个，最少一个，多者不限。先取完者胜。

局势：(ak,bk) 

前几个奇异局：(0,0)  (1,2)  (3,5)  (4,7)  (6,10)  (8,13)  (9,15)  (11,18)  (12,20)……

1.发现差值递增，且局面中第一个值为前面局面中没有出现过的数字的第一个数，且所有自然数都会出现。

2.再找规律：第一个值=(int) (差值*1.618) 而1.618 = ( sqrt(5)+1 )/2

3.所以，只要ak == (int) (bk - ak) * ( sqrt(5) + 1 ) / 2 先手必输，否则先手必胜

51nod裸题：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 double c=(sqrt(5)+1)/2; 6 int main(){ 7     int t; cin>>t; 8     int ak,bk; 9     while(t--){10         cin>>ak>>bk;11         if(ak>bk) swap(ak,bk);12         int n=(bk-ak)*c;13         if(ak==n)  puts("B");14         else  puts("A");15     }16     return 0;17 }