OpenJudge NOI题库 6266:取石子游戏

题目

• 本题的提示还是够详细了：
  假设石子数目为(a,b)且a >= b,如果[a/b] >= 2则先手必胜,如果[a/b]<2,那么先手只有唯一的一种取法.
  [a/b]表示a除以b取整后的值.
• 当x/y<2时，很显然只有一种取法
• 当x/y>=2时，这时候该走的人(S)总是能赢(如果x=k*y+r，当S为状态为[r,y]的该走的人，且其最后赢家为自己，那么S先走到[r+y,y]，O走到[r,y]，该S走，S赢；其最后赢家为对手时，那么S先走到[r,y]，该O走，那么最后的赢家就是O的对手：S)

#include<cstdio>
int cnt;
long long n,m;
void check()
{
    cnt=1-cnt;
if(m==n||n/m>=2||m/n>=2) return ;
if(n>m) n-=m;
else m-=n;
    check();
}
int main()
{
while(scanf("%I64d%I64d",&n,&m)&&n&&m){
        cnt=0;
        check();
if(cnt) printf("win\n");
else printf("lose\n");
    }
}

一开始的代码： wa了

#include<cstdio>
int cnt;
long long n,m;
void check()
{
    cnt=1-cnt;
if(!n||!m||n/m>=2||m/n>=2) return ;
if(n>m) n-=m;
else m-=n;
    check();
}
int main()
{
while(scanf("%I64d%I64d",&n,&m)&&n&&m){
        cnt=0;
        check();
if(cnt) printf("win\n");
else printf("lose\n");
    }
}

原因就在：if(!n||!m||n/m>=2||m/n>=2) return ; 中!n||!m将cnt向后推了一个人，会错。