# litlocus 题解导出

导出时间：2026/10/22 02:32:51

---

## 二次剩余平移

- 原题：圆环上的游戏
- 作者：GF1048576
- 审核时间：2026/10/21 15:38:54

设 $Q = \mathbb F_p^{\times 2}$ 为所有非零二次剩余的集合.

**命题.** 若 $a \in \mathbb F_p \setminus \{0\}$, 则 $|Q \cap (Q + a)| = \dfrac{p-3}{4}$.

*证明.* 若 $u^2 \in Q$ 而 $u^2 - a = v^2 \in Q$, 整理可以得到 $(u+v)(u-v) = a$. 遍历 $u - v \in \mathbb F_p \setminus \{0\}$ 即可得到恰好 $p-1$ 组解. 现在排除几个边界情况:

- $u = 0$ 或 $v = 0$: $u = 0$ 要求 $v^2 = -a$, $v = 0$ 要求 $u^2 = a$. 由于 $p \equiv 3 \pmod 4$, 所以 $a$ 和 $-a$ 恰好有一个是二次剩余, 因此只需要排除其中的 $2$ 组解;
- 每一组 $q \in Q \cap (Q + a)$ 对应四组 $(u, v)$: $(\pm \sqrt q, \pm \sqrt{q-a})$, 因此每组 $(u, v)$ 对应 $\dfrac 14$ 个 $Q \cap (Q+a)$ 中的元素.

综上, 
$$
|Q \cap (Q + a)| = \dfrac{p-3}{4}.
$$

---

基于这个命题, 我们证明答案等于 $k = \dfrac{p+1}{4}$. 根据以上, 有 $|Q| = 2k-1$, $|Q \cap (Q + a)| = k-1$.

### 下界

设第 $i$ 个盒子的棋子总数是 $a_i$, $V = \sum_{i \notin Q} a_i$. 若 $a = 0$, 则 $V$ 的改变量为 $0$; 若 $a \ne 0$, 则会给 $a + Q$ 中的 $k$ 个非二次剩余增加或减少 $1$ 个棋子, 故 $V$ 的改变量为 $\pm k$. 由于 $0 \notin Q$ 而 $1 \in Q$, 有 $V$ 的最终改变量为 $-m$. 而 $V$ 的每次改变量均能被 $k$ 整除, 因此 $k \mid m$, 进而 $m \ge k$.

### 上界

我们证明 $m = k$ 是可以取到的.

现在任取 $b \in \mathbb F_p$. 考虑对于任意的, 满足 $b \notin a + Q$ 的参数 $a$, 在 $a + Q$ 的坐标下添加一个棋子. 此时, 对于一个点 $x \in \mathbb F_p \setminus \{b\}$, 所有能向 $x$ 放棋子的操作一共有 $|Q| = 2k-1$ 个, 而能同时向 $b$ 放棋子的操作一共有 $|Q \cap (Q-\delta)| = k-1$ 个, 因此总共能向 $x$ 放 $k$ 个棋子.

在上文的论证中取 $b = 0$, 执行上述操作后, 根据上文论证, 对于每一个 $x \in \mathbb F_p \setminus \{0\}$ 都有 $k$ 个棋子; 然后再根据上文论证取 $b = 1$, 但是将每一步的放棋子换为取棋子, 这样相当于对每一个 $x \in \mathbb F_p \setminus \{1\}$ 取出 $k$ 个棋子, 因此最终局面变为只有 $1$ 中有 $k$ 个棋子.