欧几里德的两个后代 Stan 和 Ollie 正在玩一种数字游戏,这个游戏是他们的祖先欧几里德发明的。给定两个正整数 M 和 N,从 Stan 开始,从其中较大的一个数,减去较小的数的正整数倍,当然,得到的数不能小于 0。然后是 Ollie,对刚才得到的数,和 M,N 中较小的那个数,再进行同样的操作……直到一个人得到了 0,他就取得了胜利。下面是他们用 (25,7) 两个数游戏的过程:

Start:(25,7)

Stan:(11,7)

Ollie:(4,7)

Stan:(4,3)

Ollie:(1,3)

Stan:(1,0)

Stan 赢得了游戏的胜利。

现在,假设他们完美地操作,谁会取得胜利呢?

输入格式
本题有多组测试数据。

第一行为测试数据的组数 C。 下面 C 行,每行为一组数据,包含两个正整数 M,N(M,N<2^31)

输出格式
对每组输入数据输出一行,如果 Stan 胜利,则输出 Stan wins;否则输出 Ollie wins。
# 以上是题目,正文开始
众所周知,博弈论有一个神函数叫SG函数,今天我不讲,~~我不会~~。我用自己的方法来做这道题。

# 先手的Stan占有绝对优势。
如果输入里两个数中较大的一个除以较小的一个的结果>2。Stan稳赢,因为Stan可以分析后面的战局,减成一个合适的数字。所以大数除小数>2,就可以直接输出了。同样,大数除小数可以整除,也可以直接输出。Stan直接减成0。

拿样例解释:25 7

如果Stan想让(4,7)时自己取,就先取成(11,7),Ollie被迫取成(4,7)。Stan达到目的。

如果Stan想让(4,7)时Ollie取,就直接取成(4,7),Ollie被迫取(4,7)。Stan达到目的。

//n和m就是那两个数。
if(n<m)//n如果小于m,就交换。所以n是大数,m是小数。
{
  k=n;
  n=m;
  m=k;
}
if(n/m>1)//大数除小数>1,Stan可以控制局面
{
  cout<<"Stan wins"<<endl;
  continue;
}
if(n%m==0)//大数除小数整除,Stan直接归零秒杀。
{
  cout<<"Stan wins"<<endl;
  continue;
}

一开始看不出来的话,就只能硬刚了。如果中途碰到可以控制局面的情况,那么碰到的那个人赢。不然就一直刚到其中一个数为0。

完整代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
long long n,m,shu,hehe,k;
int main()
{
  cin>>hehe;
  for(int i=0;i<hehe;i++)
  {  
    cin>>n>>m;
    shu=0;
    if(n<m)//把n定为大数,m固定小数。
    {
      k=n;
      n=m;
      m=k;
    }
    if(n/m>1)//Stan稳赢情况
    {
      cout<<"Stan wins"<<endl;
      continue;
    }
    if(n%m==0)//Stan稳赢情况
    {
      cout<<"Stan wins"<<endl;
      continue;
    }
    while(true)//开局没有稳赢情况,开始硬刚
    {
      if(n<m)
      {
        k=n;
        n=m;
        m=k;
      }
      if(n/m>1)//控制局面点。到达者胜
      {
        if(shu%2==0)
        {
          cout<<"Stan wins"<<endl;
          break;
        }else
        {
          cout<<"Ollie wins"<<endl;
          break;
        }
      }
      if(n%m==0)//直接归零点。到达者胜
      {
        if(shu%2==0)
        {
          cout<<"Stan wins"<<endl;
          break;
        }else
        {
          cout<<"Ollie wins"<<endl;
          break;
        }
      }
      n-=m;//不会有必胜局面,只能做大数减小数的操作。
      shu++;//标记轮数。奇数轮是Ollie操作,偶数论是Stan操作,
    }
  }
return 0;
}

好的,就这么结束了。代码好2啊。

05-21 23:49