题意理解

我们有 $n$ 枚硬币，编号 $1 \dots n$，初始状态给定（0 反面朝上，1 正面朝上）。

操作规则：

1. 必须选一个当前反面朝上的硬币 $x$。
2. 将 $x$ 写成 $x = c \cdot 2^a \cdot 3^b$，其中 $c$ 与 $2,3$ 互质。
3. 有两种操作类型：
   • 类型 1（对 $a$ 操作）：选择 $p \ge 1, q \in [1,\text{MAXQ}]$，且 $a \ge pq$，翻转所有编号为 $c \cdot 2^{a - p j} \cdot 3^b$ 的硬币，$j=0,1,\dots,q$。
   • 类型 2（对 $b$ 操作）：选择 $p \ge 1, q \in [1,\text{MAXQ}]$，且 $b \ge pq$，翻转所有编号为 $c \cdot 2^a \cdot 3^{b - p j}$ 的硬币，$j=0,1,\dots,q$。

游戏结束：当无法操作时（没有反面朝上的硬币可选），当前玩家输。

---

关键观察

1. 硬币独立性
   注意到 $x = c \cdot 2^a \cdot 3^b$ 中，$c$ 是与 $2,3$ 互质的数，不同的 $c$ 之间是独立的，因为操作只改变 $a,b$ 不改变 $c$。
   所以游戏可以按 $c$ 分解成若干独立子游戏，每个 $c$ 对应一个 $(a,b)$ 的二维棋盘。

2. 状态表示
   对于固定的 $c$，所有可能的 $2^a 3^b \cdot c \le n$ 构成一个二维矩阵（$a$ 为行，$b$ 为列）。
   每个位置 $(a,b)$ 表示硬币 $c \cdot 2^a \cdot 3^b$ 是否存在（编号 $\le n$），以及它的初始状态。

3. 操作的含义

   • 类型 1：在 $(a,b)$ 处，选择一个 $p,q$ 满足 $a \ge pq$，翻转 $(a-pj, b)$ 共 $q+1$ 个位置（$j=0..q$），即一列上等间距的若干硬币。
   • 类型 2：在 $(a,b)$ 处，选择一个 $p,q$ 满足 $b \ge pq$，翻转 $(a, b-pj)$ 共 $q+1$ 个位置（$j=0..q$），即一行上等间距的若干硬币。

   操作只能在反面朝上的 $(a,b)$ 位置发起。

4. 等价于翻棋子游戏
   这是一个典型的组合博弈问题，每个 $(a,b)$ 位置如果是反面朝上，就可以发起操作，操作会翻转该行或该列上的一些位置（包括自己）。
   由于翻转两次等于没翻，这实际上是在 $\mathbb{F}_2$（异或）上的游戏。

---

SG 定理应用

整个游戏是多个独立子游戏（每个 $c$）的直和，所以总 SG 值是所有 $c$ 对应 SG 值的异或和。

对于固定的 $c$，我们考虑它的 $(a,b)$ 矩阵，矩阵大小有限（因为 $2^a 3^b \le n/c$）。

设 $\text{SG}(a,b)$ 表示在 $(a,b)$ 这个位置是反面朝上时，只考虑这个位置及其能影响的位置构成的子游戏的 SG 值。

但这里不能直接这样定义，因为操作影响多个位置。实际上，这是一个有向图游戏（Impartial Game），状态是整个矩阵的 0/1 反面状态，但状态数太大。

---

关键简化

注意到：

• 操作总是从某个 $(a,b)$ 出发，沿着 $a$ 递减或 $b$ 递减的方向影响一串位置。
• 每次操作翻转的是一串位置，相当于改变这些位置的反面/正面状态。
• 在组合博弈中，这种“翻转多个位置”的游戏，如果每次操作必须包含某个特定位置（这里是初始的反面位置），并且操作集合与状态独立，那么可以建模为 Nim 类游戏。

事实上，这个游戏是 Moore’s Nim$_q$ 的一个二维推广，但这里 $q$ 是变化的。

---

已知结论

这个游戏在 2012 年左右的 ACM 竞赛中出现过类似题（基于 2,3 的因子分解 + 翻硬币）。
其结论是：

1. 每个 $c$ 对应一个二维棋盘，可以按 $(a,b)$ 计算它的 Grundy 数。
2. 由于操作是线性的（在 $\mathbb{F}_2$ 上），可以用 nimber 计算。
3. 最后发现，每个 $(a,b)$ 的 SG 值只与 $a,b$ 有关，与 $c$ 无关，并且满足：

$$\text{SG}(a,b) = \text{mex}_{p\ge 1, 1\le q\le Q, pq \le a} \left( \bigoplus_{j=0}^q \text{SG}(a-pj, b) \right) \ \ \bigcup \ \ \text{mex}_{p\ge 1, 1\le q\le Q, pq \le b} \left( \bigoplus_{j=0}^q \text{SG}(a, b-pj) \right) $$

初始 $\text{SG}(0,0)$ 需要单独考虑（没有操作，SG=0）。

4. 对于初始状态，如果硬币 $c 2^a 3^b$ 是正面朝上，则它不参与 SG 异或；如果是反面朝上，则它的 Grundy 值 $\text{SG}(a,b)$ 参与总异或。

所以总 SG = $\bigoplus_{c} \bigoplus_{a,b\ \text{s.t. coin state=0}} \text{SG}(a,b)$。

若总 SG ≠ 0，Alice 胜，否则 Bob 胜。

---

算法步骤

1. 预处理 $\text{SG}(a,b)$ 对于 $a,b$ 在一定范围内的值（因为 $2^a 3^b \le n \le 30000$，所以 $a \le \lfloor \log_2 n \rfloor \approx 15$，$b \le \lfloor \log_3 n \rfloor \approx 10$，矩阵很小）。
2. 对每个测试数据：
   • 初始化总异或和 = 0。
   • 对每个硬币 $i$，分解 $i = c \cdot 2^a \cdot 3^b$，找到 $c,a,b$。
   • 如果硬币初始状态为 0（反面朝上），则总异或和 ^= $\text{SG}(a,b)$。
3. 若总异或和 ≠ 0，输出 "win"，否则 "lose"。

---

时间复杂度

• 预处理 SG 表：$O(A \cdot B \cdot \text{MAXQ} \cdot (A+B))$，其中 $A \approx 15, B \approx 10$，很小。
• 处理每组数据：$O(n)$ 分解质因数（只需除 2,3）。