题解 | #【模板】巴什博弈#

题解：BISHI35 【模板】巴什博弈

题目链接

【模板】巴什博弈

题目描述

有一堆石子，双方轮流取走石子。设初始石子数为 $N$ ，每次可以取走 $1$ 到 $M$ 颗（即至多 $M$ 颗），拿到最后一个石子者获胜。给出多组数据 $(N,M)$ ，判断先手是否必胜，输出 YES/NO。

解题思路

经典巴什博弈。关键在于把局面维持在 $M+1$ 的倍数：

若 $N\equiv 0\pmod{M+1}$ ，则无论先手取 $x\in[1,M]$ ，都会留给后手 $N-x\equiv -x\not\equiv 0\pmod{M+1}$ 的必胜态；
若 $N\not\equiv 0\pmod{M+1}$ ，先手一次取 $x\equiv N\bmod (M+1)$ （且 $1\le x\le M$ ），把局面送到 $(M+1)$ 的倍数，之后先手始终“对称”到 $M+1$ ，最终拿到最后一颗。

结论：先手必胜当且仅当 $N\bmod(M+1)\ne 0$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        long long N, M;
        cin >> N >> M;
        cout << (N % (M + 1) == 0 ? "NO" : "YES") << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long N = sc.nextLong();
            long M = sc.nextLong();
            System.out.println(N % (M + 1) == 0 ? "NO" : "YES");
        }
    }
}

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    print("NO" if N % (M + 1) == 0 else "YES")

算法及复杂度

算法：巴什博弈结论，判断 $N\bmod (M+1)$ 是否为 $0$
时间复杂度： $\mathcal{O}(T)$
空间复杂度： $\mathcal{O}(1)$