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

博弈题

看到这题就想到了SG函数

那么可以考虑最终情况：一个数是x，另一个是0，那么先手必败（因为上一个人已经得到0了，其实游戏已经结束了）

剩下的情况：一个数n， 一个数m，假设n>m

那么根据题意，SG(n,m)=mex{SG(n - m, m), SG(n - 2m, m), ......, SG(m, n%m)（此处交换了顺序，因为m>n%m）}

考虑里面的SG怎么求。

可以发现，SG(n-m, m)=mex{SG(n-2m, m), SG(n-3m, m)........SG(m, n%m)}

SG(n- 2m, m)同理

所以除了SG(m, n%m)以外的SG都可以由SG（m, n%m）得来

假设SG(m, n%m)==0，设n/m=k， SG(n-(k-1)*m,m)==mex{SG(m, n%m)}=1

从此往上一直到SG(n, m)的值为2,3,4,5...，即一直必胜，简单记为1

如果SG（m, n%m）==1， 那么 SG(n-(k-1)*m,m)==mex{SG(m, n%m)}=0

剩下的依旧为2,3,4,5,6...，也可记为1

那么可以看出，如果n/m==1，SG(n, m)=！SG(m, n%m)，不然是1

这是一个标准的辗转相除的一个递推式，用GCD的写法即可实现

代码：

#include <cstdio>
#define min(a, b) (a<b? a : b)
#define max(a, b) (a<b? b : a)
int T, m, n;
bool solve(int n, int m)
{
    if (!m)return false;
    if (n/m == 1)return !solve(m, n%m);
    else return true;
}
int main()
{
    scanf("%d", &T);
    for (int xx = 1; xx <= T; xx++)
    {
        scanf("%d%d", &n, &m);
        if (solve(max(n, m), min(n, m)))
            printf("Stan wins\n");
        else
            printf("Ollie wins\n");
    }
}