这是一道基础的复杂博弈论题——我到现在都不是很能理解。
其实我也不太懂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;
}