「一本通 6.7 例 1」取石子游戏 1

题目描述

有 $N$ 颗石子，两人轮流取，每步至少取 $1$ 颗、至多取 $K$ 颗，取走最后一颗者获胜，双方都采用最优策略。输入一行两个整数 $N$ 、 $K$ （ $1\le N\le 10^5,\ 1\le K\le N$ ），先手必胜输出 1，后手必胜输出 2。样例输入 23 3，输出 1。

思路

这是巴什博弈：先手必败当且仅当 $N$ 是 $K+1$ 的倍数。若不是倍数，先手取走 $N \bmod (K+1)$ 颗，此后每轮都补足到 $K+1$ 。因此只需判断 $N \bmod (K+1)$ 是否为零，时间 $O(1)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:47
# update_at: 2026-10-01 00:48

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)

    # 巴什博弈：剩余数不是 (k+1) 的倍数即为必胜态，先手取走 n % (k+1) 颗就把它交给对手
    first_wins = n % (k + 1) != 0
    print(1 if first_wins else 2)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:38
 * update_at: 2026-10-06 01:38
 */

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    ll n; // 石子总数
    ll k; // 每步最多取走的石子数
    cin >> n >> k;

    // 巴什博弈：N 是 K+1 的倍数时先手必败，否则先手必胜
    if (n % (k + 1) != 0) {
        cout << 1 << endl;
    } else {
        cout << 2 << endl;
    }

    return 0;
}

「一本通 6.7 例 1」取石子游戏 1

目录

题目描述

思路

参考代码