思路与结论

• 这是一个和式博弈，求每堆的 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)$。

题目内容

米小游和 $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$ ，则不可以选择这一堆。