原题链接。本题有一种复杂度和欧几里得算法相同的$O(\log N)$递归算法，但也存在一种$O(1)$做法。我们首先回顾递归算法的推导过程。
考虑状态$(x, y)$，无妨设$x \ge y$。考虑带余除法$x = ky +z$。
- 如果$z = 0$，那么显然先手必胜。
- 如果$0<z<y$，下面讨论$k$的值：
- 如果$k=1$，那么唯一后继状态是$(y, z)$，则可以递归处理。
- 如果$k\ge 2$，这种情况下$(x, y)$一定先手必胜。为何？此时$(x, y)$同时存在后继状态$(y+z, y)$和$(y, z)$。下面讨论：
- 如果$(y, z)$为先手必败态，那么$(x, y)$为先手必胜态；
- 如果$(y, z)$为先手必胜态，那么$(y+z, y)$的唯一后继状态为先手必胜态，于是$(y+z, y)$为先手必败态，于是$(x,y)$又是先手必胜态。
综上，如果$f(x, y)$表示该状态是否为先手必胜，则有
$$
f(x, y) = \cases{\text{True,} \quad \text{if } x \ge 2y \text{ or } x = y, \\ \text{not } f(y, z), \quad \text{if } 0 < z = x - y < y.}
$$
现在，我们想证如下命题：$f(x, y)$值为$\text{True}$，当且仅当$x = y$或$\frac{x}{y} > \phi$，其中$\phi = \frac{\sqrt 5 + 1}{2}$。这便是本题的$O(1)$做法。
现在设$x_0 = x, x_1 = y$。无妨假设$x_0 > x_1$（即以下的讨论都撇开两者相等的情形）。展开上面的递归算法，我们发现，$f(x_0, x_1)$值为$\text{True}$，当且仅当以下某个条件成立：
- $x_0 \ge 2 x_1$；或者
- $x_0 = x_1 + x_2, x_1 = x_2 + x_3, x_2 \ge 2 x_3$，其中$0 <x_3<x_2<x_1<x_0$；或者
- $x_0 = x_1 + x_2, x_1 = x_2 + x_3, x_2 = x_3 + x_4, x_3 = x_4 + x_5, x_4 \ge 2 x_5$，其中$0 <x_5 < x_4 <x_3<x_2 <x_1 <x_0$；或者
- 一般地，存在某个$k \ge 0$，使得$x_i = x_{i+1} + x_{i+2}$对于所有的$i = 0, …, 2k-1$成立，并且$x_{2k} \ge 2 x_{2k+1}$。
同样地，$f(x_0, x_1)$值为$\text{False}$，当且仅当存在某个$k \ge 0$，使得$x_i = x_{i+1} + x_{i+2}$对于所有的$i = 0, …, 2k$成立，并且$x_{2k+1} \ge 2 x_{2k+2}$。
对于上面这些情况，我们不妨把数列$\set{x_n}$的顺序颠倒，并且重新编号。那么我们无非是在考察某个数列$\set{y_n}$的性质，其中$y_n = y_{n-1} + y_{n-2}$，并且$y_1 \ge 2 y_0$。我们可以证明该数列具有如下性质：
- $\frac{y_{2k+1}}{y_{2k}} > \phi$对于任意$k\ge 0$成立；
- $\frac{y_{2k}}{y_{2k-1}} < \phi$对于任意$k\ge 1$成立。
先考虑第一部分。设$r_n = \frac{y_n}{y_{n-1}}$。则不难得到$r_n = 1 + \frac 1 {r_{n-1}}$。进一步，
$$
r_n = 2 - \frac{1}{1+r_{n-2}}.
$$
设$g(x) = 2 - \frac 1 {1+x}$，则不难验算$\phi$是$g$的一个不动点，并且$g(x)$在$(-1, \infty)$上单调递增。因而，如果$x>\phi$，那么$g(x) > g(\phi) = \phi$。
而我们知道$r_1 = \frac{y_1}{y_0} \ge 2 > \phi$。所需结论由归纳法易得。
第二部分类似，只需注意到$r_2 = \frac{y_2}{y_1} = \frac{y_0 + y_1}{y_1} \le \frac{\frac 12 y_1 + y_1}{y_1} = \frac 32 < \phi$即可为归纳法奠基。
借用数列$\set{y_n}$的上述性质，我们发现：若$f(x_0, x_1)$值为$\text{True}$，那么存在某个$k$和$x_2, …, x_{2k+1}$满足前述关系，而我们可以把$x_{2k+1}$对应于$y_0$，$x_{2k}$对应于$y_1$，以此类推，直到$x_1$对应于$y_{2k}$，以及$x_0$对应于$y_{2k+1}$。于是一定有$\frac{x_0}{x_1} = \frac{y_{2k+1}}{y_{2k}} > \phi$。同理，若$f(x_0, x_1)$值为$\text{False}$，则一定有$\frac{x_0}{x_1} < \phi$。这就完成了我们的证明。
（注意该比值$\frac{x_0}{x_1}$是有理数，因而一定不会等于$\phi$。）