题解 P1290 【欧几里德的游戏】
顾z
2018-07-09 16:40:16
给定两个正整数M和N,从Stan开始,从其中较大的一个数,减去较小的数的正整数倍,当然,得到的数不能小于0。然后是Ollie,对刚才得到的数,和M,N中较小的那个数,再进行同样的操作……直到一个人得到了0,他就取得了胜利。
此时对于样例24 15
Start: 24 15
S:9 15
O:9 6
S:3 6
O:3 0
则Olive获胜。
通过枚举一些情况不难发现 如果n/m==1,则另一人获胜。
eg:7 6
S: 1 6
O: 1 0
如果持续出现这种情况 每次"!"即可
对于n/m!=1的情况:
我们可以有目的的选择所减数来保证自己获胜
策略:
取走(n/m-1)*m
得到(n%m+m,m)的状态。
此时对方只能取走m,
而我们可以每一局都选取状态。
——————————————————————————————摘自《信息奥赛数学一本通》
```cpp
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define IL inline
#define RI register int
using namespace std;
int T,n,m;
IL void read(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
IL void print(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int main()
{
read(T);
for(;T;T--)
{
read(m),read(n);
bool f=true;
if(m<n)swap(m,n);
while(m/n ==1 && m%n)
{
//cout<<m<<" "<<n<<endl;
//cout<<endl;
int t=m%n;
m=n;
n=t;
f=!f;
}
if(f)printf("Stan wins\n");
else printf("Ollie wins\n");
}
}
```