lp1290 欧几里德的游戏

这是一道基础的复杂博弈论题——我到现在都不是很能理解。
其实我也不太懂SG函数，我就口chao胡xi一下这题的做法吧。
对于\(x,y st: x<y\)，我们定义对于x,y的SG函数SG(S)，其中S是一个局面。 我们定义关于一个局面S的后继S’，使得S’可以从S转移得到。 所以我们定义一个集合T，包含了局面S的所有后继的SG值。 对于必败局面，我们令它的SG值为0，否则为1。 则\(SG(S)=mex(T)\)，其中mex表示最小的不在集合中的非负整数。 所以， $$SG(x,y)=mex(SG(x,y-x),SG(x,y-2*x),$$

$$SG(x,y-3*x)…SG(x,y%x))$$ 我们又知道，对于其中的每一个SG函数，递推式都是成立的。 所以事实上，当\(x/y>1时，SG(x,y)=1\)，这是因为当\(x/y==1\)始终是等于\(!(SG(y%x,x))\)
所以事实上\(SG(x,y)\)只取决于\(SG(x,y%x)\)的值。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int a,b;

inline bool SG(int x,int y){
    if(!x){
        return 0;
    }
    if(y/x==1){
        return !SG(y%x,x);
    }else{
        return 1;
    }
}
void init(){
    scanf("%d%d",&a,&b);
    bool bo=SG(Min(a,b),Max(a,b));
    if(bo){
        puts("Stan wins");
    }else{
        puts("Ollie wins");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}