题目分析

这是一个两人轮流进行的石子合并游戏：

• 初始有 $n$ 堆石子，每堆 1 个
• 每次操作可以选择两堆石子合并（要求合并后不超过 $m$）
• 无法操作的一方输掉游戏
• 小 Z 先手，问谁会获胜

解题思路

通过分析游戏规律，发现游戏的胜负只与可进行的操作次数有关：

1. 操作次数分析：每次合并减少一堆石子，但受限于 $m$ 的值
2. 最大堆数：最多能形成 $\lfloor n/m \rfloor$ 堆大小为 $m$ 的石子堆
3. 实际操作次数：总操作次数为 $n - \text{最大堆数} - \text{调整项}$
4. 胜负判断：操作次数为奇数时先手胜，偶数时后手胜

关键公式

设 $t = \lfloor n/m \rfloor$，则：

• 如果 $n \bmod m \neq 0$，操作次数 $r = n - t - 1$
• 如果 $n \bmod m = 0$，操作次数 $r = n - t$

综合为：$r = n - t - (n \bmod m \neq 0)$

完整代码

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        int t = n / m;
        int r = n - t - (n % m != 0);
        
        if (r & 1) {
            cout << 0;
        } else {
            cout << 1;
        }
        
        cout << "\n";
    }
    
    return 0;
}

代码说明

• t = n / m：计算最多能形成的大小为 $m$ 的石子堆数
• r = n - t - (n % m != 0)：计算实际可进行的操作次数
• r & 1：判断操作次数的奇偶性
• 输出 0 表示先手胜，1 表示后手胜

算法复杂度

• 时间复杂度：$O(T)$，每组数据只需常数时间计算
• 空间复杂度：$O(1)$，只使用固定数量的变量

示例验证

以样例输入为例：

n=7, m=3: t=2, r=7-2-1=4(偶数) → 后手胜(1)
n=1, m=5: t=0, r=1-0-1=0(偶数) → 后手胜(1)  
n=4, m=3: t=1, r=4-1-1=2(偶数) → 后手胜(1)
n=6, m=1: t=6, r=6-6-0=0(偶数) → 后手胜(1)
n=2, m=2: t=1, r=2-1-0=1(奇数) → 先手胜(0)