我的算法书 - 欧几里德的游戏

这是一个非常经典的博弈论题目，通常被称为 “欧几里得博弈” (Euclid’s Game)。

它的核心解法基于我们熟悉的欧几里得算法（辗转相除法），但加入了博弈的策略成分。

下面我为你提供详细的题目解析、解题思路以及代码实现。

1. 题目核心分析

这个游戏是公平组合游戏（Impartial Game），即两人面对同一局面，规则相同，且信息完全公开。我们需要判断当前状态是必胜态（Winning Position）还是必败态（Losing Position）。

设定当前状态为 $(M, N)$ ，且假设 $M \ge N$ （如果不满足则交换）。

游戏的操作是从 $M$ 中减去 $N$ 的倍数。这就很像求最大公约数的过程： $M \% N$ 。但是，普通的欧几里得算法是直接算 $M \% N$ （即减去尽可能多的 $N$ ），而在游戏中，玩家可以选择减去 $1$ 个 $N$ ，或者 $2$ 个 $N$ ，直到不能减为止。

我们可以把局面分为三种情况讨论：

情况一： $M$ 是 $N$ 的倍数 ( $M \% N == 0$ )

如果 $M$ 能被 $N$ 整除（例如 15 和 5），当前玩家可以直接减掉 $k \times N$ 使得结果为 0。根据规则，谁先得到 0 谁赢。 结论：必胜。

情况二：只能减去一次 ( $N < M < 2N$ )

例如 $(7, 4)$ ，因为 $7 < 4 \times 2$ ，玩家只能选择减去 $1$ 个 4，变成 $(3, 4)$ 。此时玩家没有选择权，是被迫进入下一个状态。 结论：当前局面的胜负，完全取决于下一个局面 $(N, M-N)$ 的胜负（胜负关系反转）。

情况三：自由选择权 ( $M \ge 2N$ )

这是题目的核心。例如 $(25, 7)$ ，即 $25 \ge 2 \times 7$ 。当前玩家有两种关键选择：

直接进入下一层：减去最大倍数，把局面变成 $(25 \% 7, 7) = (4, 7)$ 给对手。
构造“必败态”给对手：只减去 (最大倍数 - 1)，把局面变成 $(25 \% 7 + 7, 7) = (11, 7)$ 给对手。

为什么这能必胜？ 如果你发现局面 $(4, 7)$ 是必败态，那你就选策略1，把必败态丢给对手，你赢。如果你发现局面 $(4, 7)$ 是必胜态，那你就选策略2。此时对手面对 $(11, 7)$ 。注意 $11 < 7 \times 2$ ，对手处于情况二，他别无选择，只能减去 7，把局面 $(4, 7)$ 又还给了你！此时轮到你面对必胜态，你赢。

简而言之，当 $M \ge 2N$ 时，当前玩家掌握了控制权。他可以根据后续局面的胜负情况，选择让自己赢的路径。 结论：必胜。

2. 算法流程

基于上面的分析，我们可以设计出算法：

设当前两个数为 $a, b$ (保持 $a \ge b$ )。从先手（Stan）开始，轮流进行判断：

如果 $b == 0$ ，游戏结束（理论上输入是正整数，不会初始为0，这步是防御性编程）。
必胜判断：
- 如果 $a \% b == 0$ （成倍数，直接拿光）；
- 或者 $a \ge 2 \times b$ （有控制权，必赢）；
- 当前玩家胜利，游戏结束。
状态转移：
- 如果不满足上述必胜条件（即 $b < a < 2b$ ），玩家被迫减去 $b$ 。
- 新状态变为 $(b, a - b)$ 。
- 交换行棋权（轮到下一位），继续循环。

3. 代码实现 (C++)

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

        #include <iostream>
#include <algorithm>

using namespace std;

// 分析函数：判断当前先手是否必胜
void solve() {
    long long m, n; // 使用 long long 防止溢出，虽然题目说 < 2^31，但在计算中更安全
    cin >> m >> n;
    
    // 保证 m 是较大的那个数
    if (m < n) swap(m, n);

    bool stan_turn = true; // 标记当前是否是 Stan 的回合

    while (n != 0) { // 只要较小的数不为0，游戏继续
        // 情况1 & 情况3:
        // 如果 m 是 n 的倍数，或者 m 足够大(>= 2n)可以让当前玩家掌握控制权
        // 那么当前玩家必胜
        if (m % n == 0 || m >= 2 * n) {
            break; // 当前玩家赢了，跳出循环
        }

        // 情况2: n < m < 2n
        // 只能减去一个 n，没得选，进入下一轮，交换对手
        long long temp = m - n; // 新的数
        m = n;                  // 较大的数变成原来的 n
        n = temp;               // 较小的数变成余数
        
        stan_turn = !stan_turn; // 只有在被迫操作时，才会交换回合且无法分出胜负
    }

    if (stan_turn) {
        cout << "Stan wins" << endl;
    } else {
        cout << "Ollie wins" << endl;
    }
}

int main() {
    int c;
    cin >> c;
    while (c--) {
        solve();
    }
    return 0;
}

4. 复杂度分析

时间复杂度：该算法本质上和欧几里得算法（求GCD）是一样的。虽然我们在 $M \ge 2N$ 时直接判赢了，但在 $M < 2N$ 时就是在做辗转相减。其复杂度是对数级别的 $O(\log(\min(M, N)))$ 。对于题目中的 $2^{31}$ 数据，这是瞬间完成的。
空间复杂度： $O(1)$ ，只需要常数个变量。

5. 总结

这道题的关键在于识破 $M \ge 2N$ 这一特殊状态。

$M < 2N$ ：类似 “听天由命”，只能被迫走一步，看下一轮结果。
$M \ge 2N$ ：就是 “我命由我不由天”，无论后续状态好坏，我都能通过策略将其转化为对我有力的局面，从而必胜。

目录