思路与结论

• 这是一个和式博弈，求每堆的 Sprague–Grundy 值再按 Nim 异或。
• 关键结论：单堆位置 $a$ 的 SG 值为 $v_2(a)$，即 $a$ 的二进制末尾连续零的个数（$a$ 中因子 $2$ 的幂次）。
• 因而整局的 Nim 异或为 $\bigoplus_{i=1}^n v_2(a_i)$。若异或不为 $0$，先手胜（输出 Baobao），否则后手胜（输出 Zeeman）。

证明要点

• 记 $a=2^t\cdot m$ 且 $m$ 为奇数，则 $v_2(a)=t$。

• 若 $a$ 为奇数（$t=0$），所有合法 $d$ 为奇数，故 $a-d$ 一定为偶数，其 SG 值均 $\ge 1$，因此 mex 为 $0$，即 $g(a)=0=v_2(a)$。

• 若 $a$ 为偶数（$t\ge 1$），对任意 $s\in[0,t-1]$，取 $d=2^s$（显然 $d\mid a$ 且 $d<a$），则

  $$a-d=2^s\bigl(2^{t-s}m-1\bigr)$$

  括号内为奇数，故 $v_2(a-d)=s$。可达的 SG 值覆盖 $\{0,1,\dots,t-1\}$。另一方面，若取 $d=2^t\cdot u$（$u\mid m,\,u<m$），则

  

  因而不可达 $t$。据此 $mex$ 为 $t$，即 $g(a)=t=v_2(a)$。

C++

#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--) {
		int n;
		cin >> n;
		unsigned xorv = 0;
		for (int i = 0; i < n; ++i) {
			unsigned x;
			cin >> x;
			// v2(x) 等于二进制末尾连续0的个数；x>0，使用 __builtin_ctz 安全
			xorv ^= __builtin_ctz(x);
		}
		cout << (xorv ? "Baobao" : "Zeeman") << '\n';
	}
	return 0;
}

Python

import sys

def v2(x: int) -> int:
    # 计算二进制末尾0个数：利用最低位1的位置
    return (x & -x).bit_length() - 1

data = sys.stdin.read().strip().split()
it = iter(data)
T = int(next(it))
out = []
for _ in range(T):
    n = int(next(it))
    xorv = 0
    for _ in range(n):
        a = int(next(it))
        xorv ^= v2(a)
    out.append("Baobao" if xorv != 0 else "Zeeman")
print("\n".join(out))

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int T = fs.nextInt();
		StringBuilder sb = new StringBuilder();
		while (T-- > 0) {
			int n = fs.nextInt();
			int xorv = 0;
			for (int i = 0; i < n; i++) {
				int a = fs.nextInt();
				// v2(a) 等于二进制末尾0；a>=1，numberOfTrailingZeros 安全
				xorv ^= Integer.numberOfTrailingZeros(a);
			}
			sb.append(xorv != 0 ? "Baobao" : "Zeeman").append('\n');
		}
		System.out.print(sb.toString());
	}

	// 轻量快速读入
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, sgn = 1, x = 0;
			do { c = read(); } while (c <= 32);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > 32) {
				x = x * 10 + (c - '0');
				c = read();
			}
			return x * sgn;
		}
	}
}

题目内容

米小游和 $Zeeman$ 又在玩游戏了。他们面前有 $n$ 堆石子，其中第 $i$ 堆有 $a_i$ 个石子。两人需要轮流从这些石子里面取，由米小游先行。轮到某个玩家取石子时，必须满足以下规则：

• 首先，玩家选择一个下标 $i$ ，且 $a_i>1$ ；

• 接下来，玩家需要选择一个正整数 $d$ 满足 $d<a_i$ 且 $a_i≡0(mod$ $d)$ 换句话说，找到一个比 $a_i$ 小且能整除 $a_i$ 的正整数 $d$ )，并从第 $i$ 堆里取走 $d$ 个石子。如果没有满足条件的 $d$ ，则不可以选择这一堆。

如果轮到某个玩家时，他无法取走任何石子，则另一个玩家胜利。

如果 米小游 和 $Zeeman$ 都采取最佳策略，请你判断游戏的胜者。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤T ≤10^4)$ 代表数据组数，每组测试数据描还如下：

第一行输入一个整数 $n(1 ≦n≦2·10^5)$ ，表示石子的堆数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≦a_i< 2^{30})$ ，代表每堆石子的数量。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2·10^5$ 。

输出描述

对于每组测运效据，输出一行一个字符串：如果来小游是胜者，则输出 $Baobao$ ，否则输出 $Zeeman$ 。

样例1

输入

5
2
4 4
1
2
2
114514 1919810
5
16 48 22 12 24
2
4 2

输出

Zeeman
Baobao
Zeeman
Zeeman
Baobao

说明

在最后一组测试数据中，米小游先手可以选择 $i=1$ 和 $d=2$ ，即从第一堆中取走 $2$ 个石子，当前石子状态变为 {$2,2$} 。这时，无论 $Zeeman$ 选择哪一堆，他都只能取走该堆中的 $1$ 个石子。米小游只需要从另一堆中也取走 $1$ 个石子将石子状态变为 {$1,1$} 。这时 $Zeeman$ 无法取走任何石子，米小游获胜。