「洛谷 P1290」欧几里德的游戏

• 局面 $(x,y)~~~x,y\geq0$
• 操作 $(x,y)\rightarrow(x-\lambda y, y)~~(x-\lambda y,y\geq0)$
• $(x,0)$ 是败

给出 $(x,y)$ 求是否为先手必胜

---

为了书写方便 $\operatorname{SG}$ 记为 $f$

首先

$$\begin{aligned} f(x,0)&=0\\ f(x,y)&=f(y,x) \end{aligned}$$

接下来考虑 $(x,y)~~x>y$

$$f(x,y)=\operatorname{mex}\{f(x-y,y),f(x-2y,y),\cdots,f(y, x \bmod y)\}$$

发现

$$f(x-y,y)=\operatorname{mex}\{f(x-2y,y),\cdots,f(y, x \bmod y)\}$$

也就是说 $f(x,y)$ 的状态由 $f(y, x\bmod y)$ 决定

若 $f(y,x\bmod y)=0$

则 $f(x\bmod y +y, y)=1$

更进一步 $f(x\bmod y+\lambda y, y) > 0$

若 $f(y, x\bmod y)>1$

则 $f(x\bmod y+y,y)=0$

但是 $f(x\bmod \lambda y, y)>,\lambda\geq 2$

综上

$x\ge x\bmod y+2y\Leftrightarrow \lfloor \frac{x}{y}\rfloor\geq2$ 时 $f(x,y)>0$

$\lfloor \frac{x}{y}\rfloor=1$ 时 $f(x,y)=\operatorname{mex}\{f(x\bmod \lambda y,y)\}$

从胜负关系考虑

$$f(x,y)=\left\{ \begin{aligned} &f(y,x)&x<y\\ &1&\lfloor \frac{x}{y}\rfloor\geq2\\ &0&y=0\\ &\neg f(y,x\bmod x)&\lfloor \frac{x}{y}\rfloor=1 \end{aligned} \right.$$

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

bool gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    if (b == 0) return 0;
    if (a / b == 1) return !gcd(b, a % b);
    return 1;
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int T;
    cin >> T;
    ll a, b;
    while (cin >> a >> b)
        cout << (gcd(a, b) ? "Stan wins\n" : "Ollie wins\n");
    return 0;
}