# 课前零食：开关与错开的时钟

> 这是一份双拼零食。前半杯问“很多开关怎样一起满足条件”，后半杯问“两个不同周期什么时候再次对齐”。它们表面不像，骨子里都在做一件事：保留约束、消掉多余自由度。

## 本节目标

学完后，你能：

- 把“按一次算翻转”翻译成 XOR 线性方程；
- 解释高斯消元的行变换为什么不改变解集，并用秩判断无解/多解；
- 把同余 $x\equiv a\pmod m$ 读成一个按周期响的时钟；
- 手推两个同余条件的合并，并知道非互质模数何时冲突。

## 前置知识与课前自测

前置：方程、模运算、XOR、最大公因数。

1. 两次按同一个翻转开关后，灯的状态为什么回到原处？
2. 方程 $x+y=1$ 与 $x+y=1$ 写两遍，会提供两条独立信息吗？
3. $x\equiv1\pmod4$ 与 $x\equiv2\pmod6$ 有公共解吗？

<details><summary>答案</summary>

1. 在 XOR 世界中 $1\oplus1=0$。2. 不会，第二行完全重复。3. 没有；两边对 $\gcd(4,6)=2$ 的余数不同，分别是 1 和 0。

</details>

## 互动规则：每个符号都要翻译回一个约束

这节分成两个工作台。开关台上，`x_i=0/1` 不是抽象字母，而是“第 i 个开关按/不按”；每一行方程是一盏灯的要求。时钟台上，`x≡a (mod m)` 不是公式，而是“从 a 开始每隔 m 出现一次”的时间点列。

每次变形都要写一张收据：**变形前哪些答案可行，变形后是否恰好还是这些答案？**不能回答这句时，先不要做下一步消元或合并。

## 从零搭框架：先枚举小世界，再把重复候选压成约束

### 第 0 步：三个开关时，人脑能枚举什么

令 `x1,x2,x3` 表示三个开关是否按。要求是：

$$
x_1\oplus x_2=1,\qquad x_2\oplus x_3=0.
$$

请列出 `000` 到 `111` 的八种按法，先筛第一条约束，再筛第二条。把留下的按法写出来。

> 停顿 0：如果变成 30 个开关，枚举从哪里爆炸？两条方程里哪一个变量出现了两次、可能被消掉？

<details><summary>展开：从候选表到行</summary>

合法按法有 `100` 与 `011`。30 个开关有 $2^{30}$ 种候选，不能逐份测试。两式都含 `x2`，把两边同时 XOR 就得到 `x1 xor x3 = 1`，并没有列举任何新候选，却把共同变量消掉。

</details>

### 第 1 步：先验证“行 XOR 行”没有偷偷改题

给第一行取一组满足它的值，给第二行也取同一组值。若两行都成立，把等式左右各 XOR 一次，结果一定成立吗？反过来，若第一行与“第一 XOR 第二行”成立，能否再 XOR 第一行恢复第二行？

> 停顿 1：这两句构成了什么样的双向证明？为什么它比“消元看起来合理”更可靠？

<details><summary>展开：初等行变换保留解集</summary>

两行同时成立时 XOR 后成立；已知第一行和 XOR 后的行，再 XOR 第一行便恢复第二行。因此替换一行不会增解也不会漏解，是解集等价变换。交换两行也只是换顺序。消元每一步都应靠这样的可逆/等价理由站住。

</details>

### 第 2 步：让主元和秩从纸上的阶梯长出来

把三行写成增广矩阵：

```text
1 1 0 | 1
0 1 1 | 0
1 0 1 | 1
```

先在第 1 列找一个 1 当主元，再用它 XOR 掉第 3 行第 1 列；随后处理第 2 列。每处理一列，在纸上圈出一个“首次独立约束”。

> 停顿 2：最后若出现 `0 0 0 | 1`，它翻译成什么人话？若某列从头到尾没主元，哪个变量得到什么自由？

<details><summary>展开：秩是独立约束数</summary>

全 0 系数配 1 是 `0=1`，无解；没有主元的列对应可自由选择的变量。相容时，秩等于独立方程数；变量数减秩就是自由度。XOR 域中主元非零只能是 1，所以用整行 XOR 即可消去。

</details>

### 第 3 步：换到时钟台，先真的把时间点列出来

写两行时间：

```text
x ≡ 1 (mod 4): 1, 5, 9, 13, ...
x ≡ 3 (mod 6): 3, 9, 15, ...
```

请圈出第一次相交，再写出下一次相交。然后把第一个条件写成 `x=1+4t`，代入第二个条件。

> 停顿 3：为什么不必继续从 0、1、2、3……逐个试？新变量 t 代表什么动作？

<details><summary>展开：CRT 也在压缩候选表</summary>

相交为 9、21，周期为 12。`t` 表示沿第一个时钟每跳一次 4 的次数；代入把“所有满足第一个条件的候选”压成一个关于 t 的同余。求 t 后就一次性得到共同候选，而不是枚举时间线。

</details>

### 第 4 步：非互质时先检查两只时钟能否对齐

比较：

$$
x\equiv1\pmod4,\ x\equiv3\pmod6
$$

与：

$$
x\equiv1\pmod4,\ x\equiv2\pmod6.
$$

请分别把两边对 2 的余数写出来。为什么第一对有机会、第二对永远无机会？

<details><summary>展开：gcd 是共同刻度</summary>

模 4 与模 6 都按 2 的共同刻度重复。第一对余数均为 1，兼容；第二对一个为 1、一个为 0，冲突。一般先检查 $g=\gcd(m,n)$ 是否整除 $b-a$，通过后才能除掉共同因子、在互质模数下求逆。

</details>

### 第 5 步：写出两条框架主线

| 工作台 | 原始暴力对象 | 新状态/摘要 | 合法变形 | 最终判断 |
|---|---|---|---|---|
| 开关 |  |  |  |  |
| 时钟 |  |  |  |  |

<details><summary>展开：它们都在维护解集合</summary>

开关从 $2^n$ 赋值到矩阵行与主元，靠等价行变换，判断无解/秩/自由度；时钟从一长串候选时间到“余数 + 模数”，靠兼容合并，判断无解或新的周期。两者不必硬说成同一算法，但都要求每一步不改变可行解集合。

</details>

## 问题动机：枚举按法和枚举日期都长得很快

有 $n$ 个开关时，“按/不按”已有 $2^n$ 种组合；有两个周期很大的时钟时，从 0 开始逐个试时间也可能要等很久。两类暴力都在重复探索同一个约束空间。我们要学会合并约束，而不是逐个候选试探。

![XOR 方程用行变换消去变量](../插图/10-高斯消元与CRT/00-代数-01-XOR消元.svg)

## 步步式引导

### 1. 开关：把“是否按”当成变量

令 $x_i\in\{0,1\}$ 表示第 $i$ 个开关是否按。某盏灯被若干开关影响，要求最终翻成目标状态，就是这些 $x_i$ 的 XOR 等于 0 或 1。例如：

$$
x_1\oplus x_2=1,\qquad x_2\oplus x_3=0.
$$

两条方程 XOR 在一起相当于“左右两边同时加同一式子”，解集不变，却能消掉共同变量。交换方程、用一行 XOR 另一行，都是不改变解集的合法行变换。

```text
row = 0
for each column col:
    find a row p >= row with matrix[p][col] = 1
    if no p: this variable is free; continue
    swap matrix[p], matrix[row]
    for every other row r with matrix[r][col] = 1:
        matrix[r] = matrix[r] XOR matrix[row]
    row += 1
rank = row
```

若得到 `0 = 1`，无解；若相容且秩等于变量数，每个变量被钉死；若秩较小，有自由变量。XOR 域里非零主元永远是 1，不需要除法。

### 2. 时钟：先让一个周期负责移动

要合并：

$$
x\equiv a\pmod m,\qquad x\equiv b\pmod n,
$$

从第一个条件出发，所有候选写成 $x=a+mt$。代入第二个条件，得到：

$$
mt\equiv b-a\pmod n.
$$

若 $g=\gcd(m,n)$ 不整除 $b-a$，两只时钟永远错开；若能整除，先除以 $g$，此时 $m/g$ 与 $n/g$ 互质，可用扩展欧几里得找到 $m/g$ 在模 $n/g$ 下的逆元，解出 $t$。

![两个周期在兼容时重新对齐](../插图/10-高斯消元与CRT/00-代数-02-时钟对齐.svg)

```text
merge(a mod m, b mod n):
    g = gcd(m, n)
    if (b - a) % g != 0: return impossible
    solve t = ((b-a)/g) * inverse(m/g mod n/g) mod (n/g)
    x = a + m * t
    return x mod lcm(m,n), lcm(m,n)
```

## 纸上模拟：两次消元、一次合并，都写出收据

先对增广矩阵做两步：`R3 ^= R1`，再用第 2 行消去第 1、3 行的第 2 列。每步写下矩阵与“为什么解集不变”。然后合并 `1 mod 4` 与 `3 mod 6`：

| CRT 阶段 | 式子 | 得到的信息 |
|---|---|---|
| 参数化 | `x=1+4t` |  |
| 代入第二条件 |  |  |
| gcd 兼容性 |  |  |
| 解出 t |  |  |
| 新余数/模数 |  |  |

<details><summary>展开：不要省略兼容性这一行</summary>

消元最后得到一条重复行，秩为 2、有一个自由变量。CRT 中 $1+4t≡3\pmod6$，即 $4t≡2\pmod6$；gcd 为 2 且整除 2，约为 $2t≡1\pmod3$，得 $t≡2\pmod3$，最小 $x=9$，新模数 $operatorname{lcm}(4,6)=12$。若兼容性失败，后面“求逆”根本没有许可。

</details>

反复合并就得到中国剩余定理（Chinese Remainder Theorem, CRT）的多条件版本。互质只是最常见的简化情况，不是非互质时可以假装不存在的细节。

## 核心知识：每一步都要保留“解集合”

高斯消元中，一行代表一个约束；合法行变换不增不减满足全部约束的变量赋值。CRT 中，一个同余代表一串等间隔候选；合并后返回的是同时满足两串候选的更稀疏序列。两者都能用“新表达和旧表达等价吗”检查正确性。

XOR 消元若有 $e$ 条方程、$v$ 个变量，朴素复杂度约 $O(ev\min(e,v))$；位集优化可加速整行 XOR。逐步 CRT 的整数乘法可能溢出，模数累乘前要确认题目范围或使用更宽整数。

## 实现指南

- 明确数域：实数、模质数、XOR 的“加法/除法”规则不同，不能只换一个 `%`。
- 扫描矛盾行时要看系数全 0 且常数非 0；不要仅凭 `rank` 猜无解。
- CRT 合并后把余数规范到 `[0, modulus)`；负的 `%` 在 C++ 里需要修正。
- 求逆前先确认互质；不存在逆元时，先按 gcd 约掉而不是硬做快速幂。

## 互动小实验室

运行 [开关与错开的时钟.py](../../互动程序/10-高斯消元与CRT/00-开关与错开的时钟.py)。选 `x` 会显示每次选主元和 XOR 消元后的矩阵；选 `c` 会逐步合并两组同余，并显示 gcd 兼容性检查。

请先预测预设 CRT 中 $x\equiv1\pmod4, x\equiv3\pmod6$ 的最小非负解，再让程序验算每个余数；再把第二个余数改成 2，看看冲突在哪一步暴露。

## 扩展与联系

高斯消元会通向解空间、线性基和图的环空间；CRT 会通向周期事件、模方程和状态压缩。二者都只在相应代数结构中正确：模合数下不是每个非零数都有逆元，带负权图也不是线性方程——不要给每个困难问题都套一副代数眼镜。

## 总结与自检

1. XOR 消元为什么允许“某一行 XOR 到另一行”？
2. 秩小于变量数且没有矛盾行，为什么会有多解？
3. CRT 合并中 `(b-a) % gcd(m,n)` 检查到底比较了什么？

<details><summary>自检答案</summary>

对等式两边同时 XOR 同一式不改变真假；至少有一个变量没被独立约束固定；两个余数在共同周期单位上是否一致。

</details>

## 一周预热安排

- 第 1 天：写三变量 XOR 方程，手动 XOR 两行消掉一个变量。
- 第 2 天：构造一行 `0=1`，辨认无解。
- 第 3 天：在数轴上列出两个小模数的余数序列。
- 第 4 天：运行互动程序，分别观察秩与 gcd 的作用。
- 第 5 天：进入[高斯消元正式课](01-高斯消元秩解空间与XOR系统.md)，再读 CRT 小节。