欧几里德的两个后代 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啊。