1122: 取石子游戏II
Time Limit: 1 Sec Memory Limit: 128 MB
Description
一堆石子有n个,两人轮流取.每次取最少取1个,最多取m个。取完者胜.先取者负输出"Second win".先取者胜输出"First win"
Input
多组测试数据。
每组测试数据包含2个正整数n,m。(n,m<=10000000)
Output
对于每组测试数据，输出谁获胜.
Sample Input
2 1 3 2 3 1 Sample Output
Second win Second win First win HINT
Source
【分析】 经典的巴什博弈，这个我觉得相较于斐波那契博弈，巴什博弈更好理解一点； 归纳一句话就是：给对手留下（m+1）的倍数，自己就能赢 那么，要先手并且n%（m+1）==0的话，是不是就不可以给对手留下（m+1）的倍数了，此时，先手必败！
【代码】
#include
<iostream
>
#include
<bits
/stdc
++.h
>
using namespace std
;
int
main()
{
int n
,m
;
while(scanf("%d%d",&n
,&m
)!=EOF)
{
if(n
%(m
+1)==0)
{
printf("Second win\n");
}
else
{
printf("First win\n");
}
}
return 0;
}
