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

· · 题解

对于这道题，我们考虑什么样的状态（假设状态为（x，y）假定y>=x）可以使当前操作的这个人胜利，显然，当x==y时，当前操作的这个人必胜了；或者当y为x的倍数是，当前这个人也会获胜。除此之外呐？于是，我们接下来要考虑x>y（去掉x==y的情况）的情况。

假设y=kx+z（z为余数）

如果k>=2，那么该状态可以转移到（x,y-(k-1)x）即(x,x+z)，而(x,x+z)(z要小于x的，因为z是余数)，只能转移到(x,z)这一个状态，这个应该很好理解的。而（x,y）也可以直接转移到这个状态（y-kx），所以不论（x,x+z）这个状态还是其下一个状态（x,z）为必胜状态，(x,y)均可到达，所以当k>=2时，当前操作者必胜。

如果k<2呢？那我们只好转到下一个人操作，我们再尝试在下一个人的状态中判断这个人是否必胜。因为k<2, 所以(x,y)只能转到(z,x)这个状态。那我们只要递归下去，知道找到必胜状态，返回当前操作者即可。

代码如下：

#include <cstdio>
#include <iostream>
using namespace std;
int m,n,q;
//当前操作者为p,p为0时代表Stan操作,p为1时代表Ollie操作。
int find(int x,int y,int p)
{
    if(x==y) return p;//返回胜者.
    if(y/x>=2) return p;//返回胜者.
    else return find(y-x,x,p^1);//向下一个状态查找.
}
int main()
{
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>m>>n;
        if(m>n) swap(m,n);
        if(find(m,n,0)==0) cout<<"Stan wins"<<endl;//如果返回0,胜者为Stan,反之则为Ollie.
        else cout<<"Ollie wins"<<endl;
    }
    return 0;

}