题解 | #质数取石子游戏#

题目链接

质数取石子游戏

题目描述

有一个石子堆，包含 $N$ 个石子。Alice 和 Bob 轮流取石子，Alice 先手。每次可以取 1 个或任意质数个石子。取走最后一个石子的玩家获胜。双方都采取最优策略，判断谁会赢。

解题思路

这是一个经典的公平博弈问题 (Impartial Game)。这类问题的核心是划分“必胜态”和“必败态”。

必败态 (Losing Position, L-position): 在当前局面下，无论玩家如何操作，都会将一个“必胜态”留给对手。轮到自己时处于必败态，则必输。
必胜态 (Winning Position, W-position): 在当前局面下，玩家至少有一种操作，可以将一个“必败态”留给对手。轮到自己时处于必胜态，则必胜。

我们的目标是找出所有必败态的规律。石子数为 0 是最基本的必败态。

我们可以通过分析少量石子的情况来寻找规律：

$N=1$ : 可取 1，剩 0 (L)。这是一个必胜态 (W)。Alice 胜。
$N=2$ : 可取 2 (质数)，剩 0 (L)。这是一个必胜态 (W)。Alice 胜。
$N=3$ : 可取 3 (质数)，剩 0 (L)。这是一个必胜态 (W)。Alice 胜。
$N=4$ :
- 取 1，剩 3 (W)。
- 取 2 (质数)，剩 2 (W)。
- 取 3 (质数)，剩 1 (W)。所有操作都导向必胜态。这是一个必败态 (L)。Bob 胜。

从这里我们发现第一个必败态是 4。这引导我们提出一个猜想：一个局面是必败态，当且仅当石子数量 $N$ 是 4 的倍数。

我们可以用数学归纳法来证明这个猜想：

基础情况: 对于 $N=1, 2, 3, 4$ ，我们已经验证猜想是成立的。
归纳步骤: 假设对于所有小于 $N$ 的数，猜想都成立。
- 当 $N$ 是 4 的倍数时 ( $N \equiv 0 \pmod 4$ ): 我们需要证明这是一个必败态，即任何操作都会导向一个必胜态 (非 4 的倍数)。
  - 取 1 个石子：剩下 $N-1 \equiv 3 \pmod 4$ 。
  - 取 2 个石子 (唯一的偶质数)：剩下 $N-2 \equiv 2 \pmod 4$ 。
  - 取任意奇数质数 $p \ge 3$ ：剩下 $N-p$ 。 $N$ 是偶数, $p$ 是奇数, $N-p$ 是奇数，必不为 4 的倍数。因此，从一个 4 的倍数的局面出发，任何操作后剩余的石子数都不是 4 的倍数。根据归纳假设，这些都是必胜态。所以， $N$ 是必败态。
- 当 $N$ 不是 4 的倍数时: 我们需要证明这是一个必胜态，即至少存在一种操作，可以导向一个必败态 (4 的倍数)。
  - 若 $N \equiv 1 \pmod 4$ : 取 1 个石子，剩下 $N-1 \equiv 0 \pmod 4$ 。
  - 若 $N \equiv 2 \pmod 4$ : 取 2 个石子 (质数)，剩下 $N-2 \equiv 0 \pmod 4$ 。
  - 若 $N \equiv 3 \pmod 4$ : 取 3 个石子 (质数)，剩下 $N-3 \equiv 0 \pmod 4$ 。因此，从一个非 4 的倍数的局面出发，总能找到一种方法，使得剩余石子数是 4 的倍数。根据归纳假设，这是一个必败态。所以， $N$ 是必胜态。

最终结论: 猜想成立。Alice 作为先手，她获胜的条件是初始石子数 $N$ 不是 4 的倍数。

如果 $N \pmod 4 \neq 0$ ，Alice 获胜。
如果 $N \pmod 4 = 0$ ，Bob 获胜。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n % 4 == 0) {
            cout << "Bob" << endl;
        } else {
            cout << "Alice" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            if (n % 4 == 0) {
                System.out.println("Bob");
            } else {
                System.out.println("Alice");
            }
        }
    }
}

import sys

def solve():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        n_str = sys.stdin.readline()
        if not n_str:
            break
        n = int(n_str)
        if n % 4 == 0:
            print("Bob")
        else:
            print("Alice")

solve()

算法及复杂度

算法: 博弈论、数论
时间复杂度: 对于每组测试数据，我们只进行了一次取模和判断操作，时间复杂度为 $\mathcal{O}(1)$ 。总的时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是测试数据的组数。
空间复杂度: 没有使用额外的存储空间，空间复杂度为 $\mathcal{O}(1)$ 。