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

博弈状态分析

解决此类问题的常用方法是分析 必胜态 (N-position, Next player wins) 和 必败态 (P-position, Previous player wins)。

1. 基础状态推导：

   • 若剩余石子数 ，当前行动者无法取子，判负（虽然题目 ，但这是递归终点）。
   • 若 ，当前行动者可以一次取走所有石子，判胜（必胜态）。
   • 若 ，当前行动者必须取走 个石子。无论取走多少，剩下的石子数 必然落在 区间内。此时轮到对手行动，对手面临必胜态，可一次取完。因此， 对当前行动者而言是必败态。

2. 周期性规律：

   • 我们可以观察到，石子数量 的胜负性质呈现以 为周期的规律。
   • 必败态构造： 如果当前石子数 是 的倍数，即 。先手取走 个石子后，剩余 。由于 ，剩余部分 此时模 的余数必然不为 0。这意味着先手无论怎么走，都会把一个“非 倍数”的状态留给后手。
   • 必胜态构造： 如果当前石子数 不是 的倍数，即 ，其中 。先手可以策略性地取走 个石子。此时剩余石子数变为 ，即先手成功将“ 的倍数”这一必败态抛给了后手。

3. 最优策略总结：

   • 若先手面临的状态 满足 ，先手必胜。先手的最优策略是取走 个石子，迫使后手进入必败态。
   • 若先手面临的状态 满足 ，先手必败。无论先手如何行动，后手只要始终维持剩余石子数为 的倍数，最终必定能拿到最后一颗石子。

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

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

    int T;
    cin >> T;

    while (T--) {
        ll n, m;
        cin >> n >> m;
        if (n % (m + 1) != 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}