# CRT：从互质公式到非互质同余合并

## 本节目标

能用中国剩余定理（Chinese Remainder Theorem, CRT）合并互质同余，用扩展 CRT（exCRT）处理非互质模数，判断无解并控制乘法溢出。

## 前置知识与课前自测

前置：gcd、扩展欧几里得、模逆、线性同余。

1. 方程 $ax\equiv b\pmod m$ 何时有解？
2. 两同余模数不互质时，余数必须满足什么兼容条件？
3. 合并后新模数一定是两模数乘积吗？

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

1. 当且仅当 $\gcd(a,m)\mid b$。
2. 两余数之差能被模数 gcd 整除。
3. 不是，最小周期是 lcm；互质时才等于乘积。

</details>

## 问题动机与核心推导

已合并为

$$
x\equiv r\pmod M,
$$

再加入 $x\equiv b\pmod m$。令 $x=r+Mt$，得到

$$
Mt\equiv b-r\pmod m.
$$

设 $g=\gcd(M,m)$。若 $g\nmid(b-r)$ 无解；否则约去 $g$，`M/g` 在模 `m/g` 下可逆，求出最小非负 t。新余数为 `r+M*t`，新模数为 `lcm(M,m)`，再规范化余数。

这就是 exCRT：逐条合并，不要求模数两两互质。

## 实现指南

- 扩展欧几里得返回的逆元可能为负，统一取模。
- `M*t` 可能超过 64 位；题目未保证安全时用 `__int128` 做中间乘法。
- 最终问“严格晚于 d”时，余数 0 也可能需要加一个周期。
- 方程先约 gcd 后的模数为 1 时，唯一余数类就是 0，无需求逆。

## 精选例题 1：Biorhythms

### 来源与题意

- [POJ-1006 Biorhythms](https://vjudge.net/problem/POJ-1006)，East Central North America 1999
- 三个周期分别为 23、28、33，已知各自峰值余数及当前天 d，求 d 之后下一次三峰同日还要多少天。

<details><summary>Hint 1</summary>求 $x\equiv p(23),e(28),i(33)$。</details>
<details><summary>Hint 2</summary>三模数互质，总周期 21252；求得余数后换成严格大于 d 的代表。</details>

### Observations、Editorial 与证明

互质 CRT 给出模 21252 的唯一解类。合并余数 r 后，答案是 `(r-d) mod 21252`，若结果为 0 则取 21252，因为题目要求未来而非当天。CRT 唯一性保证该正代表是下一次而非某次更晚相遇。

### 核心伪代码与附件

```text
r, period = CRT([(p,23), (e,28), (i,33)])
days = (r - d) mod period
if days == 0: days = period
```

[完整 C++17 附件](../../参考实现/10-高斯消元与CRT/POJ-1006.cpp)

## 精选例题 2：Strange Way to Express Integers

### 来源与题意

- [POJ-2891 Strange Way to Express Integers](https://vjudge.net/problem/POJ-2891)，POJ Monthly 2006
- 多组直到 EOF；给若干 `x ≡ remainder (mod modulus)`，模数不保证互质，求最小非负解或 -1。

<details><summary>Hint 1</summary>维护当前 `(r,M)`，逐条调用上面的线性同余合并。</details>
<details><summary>Hint 2</summary>兼容条件是 `(b-r)%g==0`。</details>

### Observations

- 不能先把模数相乘：非互质会重复周期因子，也可能掩盖矛盾。
- 每次合并后的 `(r,M)` 完整代表此前所有方程，不需保存旧式子。
- 无解一旦出现，后续约束不可能修复。

### Editorial 与正确性证明

初始 `(0,1)` 表示所有整数。逐条代入 `x=r+Mt` 解线性同余；若兼容则得到所有共同解的唯一剩余类，更新为规范化的 `(r,lcm)`。归纳可知处理 k 条后恰表示前 k 条共同解集；最终 r 是最小非负解。每次 $O(\log\max modulus)$。

### 核心伪代码与附件

```text
r, M = 0, 1
for (modulus m, remainder b):
    g, inverse = extended_gcd(M, m)
    if (b-r) is not divisible by g: return -1
    t = ((b-r)/g * inverse) mod (m/g)
    r = r + M*t
    M = lcm(M,m); r %= M
```

[完整 C++17 附件](../../参考实现/10-高斯消元与CRT/POJ-2891.cpp)

## 精选例题 3：Throne

### 来源与题意

- [AtCoder-abc186_e Throne](https://vjudge.net/problem/AtCoder-abc186_e)
- 多组给 $N,S,K$，求最小非负 x 使 `(S+Kx) mod N = 0`，无解输出 -1。

<details><summary>Hint 1</summary>改写为 $Kx\equiv-S\pmod N$。</details>
<details><summary>Hint 2</summary>先除以 $g=\gcd(K,N)$，再求逆元。</details>

### Observations、Editorial 与证明

线性同余有解当且仅当 g 整除 S。约分后 `K/g` 与 `N/g` 互质，其逆元存在；乘到右侧并规范化就得到模 `N/g` 的唯一解类，最小非负代表即答案。每组 $O(\log N)$。

### 核心伪代码与附件

```text
g = gcd(K,N)
if S % g != 0: answer = -1
else:
    K,N,S = K/g,N/g,S/g
    answer = (-S * inverse(K mod N)) mod N
```

[完整 C++17 附件](../../参考实现/10-高斯消元与CRT/AtCoder-abc186_e.cpp)

## 扩展与联系

CRT 解决的是多个同一未知量的同余交集；高斯消元解决多个未知量的线性系统。模数不是质数时，多变量系统可考虑质因数分解后分别求解再 CRT，但素数幂上的消元仍需处理非单位主元。

## 总结与自检

1. exCRT 的兼容条件从哪里来？
2. 新周期为何是 lcm？
3. 严格未来查询为何把 0 改成整周期？
4. 线性同余约 gcd 后为什么可以求逆？

## 课后训练建议

枚举小模数所有 x 对拍 exCRT，覆盖兼容非互质、不兼容、某模数整除另一模数。用接近 $10^{18}$ 的数检查中间乘法是否需要 128 位。