题解 P1290 【欧几里德的游戏】

顾z

2018-07-09 16:40:16

Solution

给定两个正整数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"); } } ```