取石子游戏

题目描述

有两堆石子，两人轮流取；每次只能从较多的一堆取，取的数量必须是较少一堆的整数倍。把任意一堆取空者获胜。多组输入，每行两个正整数 $a,b$ ，以 0 0 结束。

思路

设 $a \ge b$ 。若 $b \mid a$ 或 $\lfloor a/b \rfloor \ge 2$ ，当前执子者必胜；否则唯一变为 $(b,a-b)$ 且胜负翻转，沿辗转相除链走到首个可胜局面看轮到谁。

参考代码

Python 版：

python

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#!/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-09-30 00:03
# update_at: 2026-09-30 00:03

import sys


def current_wins(a: int, b: int) -> bool:
    """(a, b) 局面下当前执子者是否必胜。

    商 a//b >= 2 时必胜（可以调整取 k 倍把必败局面留给对手）；
    a % b == 0 时直接取空一堆获胜；
    否则商为 1，只有 (a, b) -> (b, a-b) 唯一取法，胜负随轮次翻转。
    """
    a, b = max(a, b), min(a, b)                      # 保证 a >= b，较多堆是 a
    mine = True                                      # True = 起始先手执子
    while a // b < 2 and a % b != 0:                 # 商为 1 且不整除：唯一取法
        a, b = b, a - b                              # 较多堆变 b，较多堆变 a-b（更小）
        mine = not mine                              # 唯一取法后换人执子
    return mine                                      # 退出时比值 >=2 或整除：执子者获胜


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while True:
        a, b = next(data), next(data)                # 每组一行两个正整数
        if a == 0 and b == 0:                        # 0 0 结束
            break
        out.append("win" if current_wins(a, b) else "lose")

    print("\n".join(out))


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
29
30
31
32
33
34
35
36
37/**
 * 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-05 05:50
 * update_at: 2026-10-05 05:50
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

// 当前(a,b)局面（a>=b）下，执子者是否必胜
// 商>=2 或整除时当前执子者可直接获胜；否则只能(a,b)->(b,a-b)，胜负翻转
bool current_wins(ll a, ll b) {
    bool mine = true; // true 表示起始先手在此局面执子
    while (a / b < 2 && a % b != 0) { // 商为1且不整除：唯一取法
        ll nb = a - b; // 取完后较少堆变为 a-b
        a = b;
        b = nb;
        mine = !mine; // 唯一取法后换人
    }
    return mine; // 比值>=2或整除：当前执子者获胜
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a, b;
    while (cin >> a >> b) {
        if (a == 0 && b == 0) break;
        if (a < b) swap(a, b); // 保证 a 是较多堆
        cout << (current_wins(a, b) ? "win" : "lose") << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码