# 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)

## 扩展与联系

## 高阶例题：Three Traffic Lights

### 来源信息与题意

- VJudge：[AtCoder-agc050_e Three Traffic Lights](https://vjudge.net/problem/AtCoder-agc050_e)
- 原题：[AtCoder Grand Contest 050 E](https://atcoder.jp/contests/agc050/tasks/agc050_e)
- 难度：AGC 1800 分；考点：非互质 CRT、周期信息压缩、分段事件扫描

三盏信号灯同时从绿灯开始。第 $i$ 盏以 $g_i$ 秒绿、$r_i$ 秒红循环，且所有 $g_i,r_i$ 都在 $[1,10^{12}]$。求接下来

$$
(g_1+r_1)(g_2+r_2)(g_3+r_3)
$$

秒内三灯同时为绿的总时长，模 $998244353$。

<details><summary>Hint 1：一秒对应三个余数</summary>

令周期 $p_i=g_i+r_i$。时刻 $t$ 绿当且仅当 $t\bmod p_i<g_i$。三个指定余数能由同一个 $t$ 产生，当且仅当它们满足非互质 CRT 的两两兼容条件。

</details>

<details><summary>Hint 2：第 i 个余数不需要保留模 p_i 的全部信息</summary>

余数 $x_i$ 只会与另外两个余数分别比较模 $\gcd(p_i,p_j)$。因此只需保留

$$
q_i=\operatorname{lcm}(\gcd(p_i,p_j),\gcd(p_i,p_k))
=\gcd(p_i,\operatorname{lcm}(p_j,p_k)).
$$

</details>

<details><summary>Hint 3：压缩后一个余数有多少个绿色原像</summary>

对 $0\le x<q_i$，区间 $[0,g_i)$ 中与 $x$ 模 $q_i$ 同余的数有

$$
w_i(x)=\left\lfloor\frac{g_i}{q_i}\right\rfloor+[x<g_i\bmod q_i].
$$

</details>

<details><summary>Hint 4：不要枚举压缩后的总周期</summary>

令 $L=\operatorname{lcm}(q_1,q_2,q_3)$。目标变为

$$
\sum_{t=0}^{L-1}\prod_{i=1}^3 w_i(t\bmod q_i).
$$

每个 $w_i$ 在一周期内只有一次从“商加一”降到“商”。选一个函数做区间求和，只扫描另外两个函数的变化时刻。

</details>

### Observations

1. 直接枚举时间的周期可能接近三个 $10^{12}$ 数的最小公倍数；直接枚举三组绿色余数更坏。非互质 CRT 的兼容条件只看两两 gcd，这允许先删除每个余数中永远不会被比较的素因子指数。
2. $q_i$ 不是随意取一个 gcd：它必须同时保留与另外两盏灯比较所需的两个模数，因此是这两个 gcd 的 lcm。更小会合并兼容性不同的余数，更大则没有新增判断信息。
3. 压缩后的余数并非权重 1。同一个 $x\bmod q_i$ 在原绿色区间里可能有多个原像；`整商 + 一个短前缀` 精确保留了这些重数。
4. 即使 $L$ 仍很大，$w_i$ 也只是周期方波。把一个方波前缀和公式化，乘积只需在另两个方波的断点间积分。
5. 三个 $q_i$ 的素因子指数有特殊结构：每个素数的最高指数至少出现在两个 $q_i$ 中。可写成 $q_1=gab,q_2=gac,q_3=gbc$，其中 $a,b,c$ 两两互质。选择最小的 $q_i$ 做区间求和后，另外两者的断点次数由较小的两个因子控制，而不是由 $L$ 控制。

### Editorial

先令 $p_i=g_i+r_i$。三个原余数 $(x_1,x_2,x_3)$ 能由同一时刻产生，当且仅当

$$
x_i\equiv x_j\pmod{\gcd(p_i,p_j)}
$$

对每对 $i,j$ 都成立。对第 $i$ 个余数，所有会参与这些条件的信息恰合并为模 $q_i$ 的余数。于是每个压缩后兼容三元组由唯一的 $t\bmod L$ 表示，其绿色原像数为三个权重之积，得到上面的求和式。

设 `base_i=g_i//q_i`、`rem_i=g_i%q_i`，则

$$
w_i(t)=base_i+[t\bmod q_i<rem_i].
$$

选 $q_i$ 最小的一盏作为 0 号灯。对另外两盏，权重只在每个周期起点和 `起点+rem` 改变；用两个“下一断点”指针合并扫描。相邻断点 $[l,r)$ 内另外两个权重恒定，而 0 号灯可用前缀公式求和：

$$
F_i(T)=base_iT+\left\lfloor\frac{T}{q_i}\right\rfloor rem_i
+\min(T\bmod q_i,rem_i),
$$

所以区间权重和是 $F_i(r)-F_i(l)$。

最后还需恢复题目要求的长区间。每个兼容原余数组在一个 $\operatorname{lcm}(p_1,p_2,p_3)$ 周期中出现一次，而题目区间长度是 $p_1p_2p_3$，故乘上

$$
\frac{p_1p_2p_3}{\operatorname{lcm}(p_1,p_2,p_3)}.
$$

实现中可写为

$$
\gcd(p_1,p_2)\cdot\gcd(\operatorname{lcm}(p_1,p_2),p_3),
$$

并用 `__int128` 计算中间 lcm，避免乘法溢出。

### 正确性证明

1. **压缩合法且完备。** 非互质 CRT 表明兼容性仅由所有两两 gcd 同余决定；$x_i\bmod q_i$ 同时且恰好决定第 $i$ 个余数在相关两个 gcd 下的值。因此压缩既不会把不兼容三元组误合并，也不会区分兼容性完全相同的三元组。
2. **权重计数不漏不重。** $[0,g_i)$ 中每个原余数唯一落到一个 $x\bmod q_i$；整周期各贡献一次，剩余 `rem_i` 个余数再贡献一次，故 $w_i$ 正确。三个灯的原像独立选择，乘积就是该压缩三元组对应的绿色原三元组数。
3. **事件扫描等于完整求和。** 扫描边界包含另外两个权重的每一次变化，故每个半开区间内它们恒定；乘以第一盏灯在该区间的精确权重和，就得到该区间全部项。区间首尾连续、不交叠并覆盖 $[0,L)$。
4. **恢复次数正确。** 每个兼容原三元组由 CRT 给出模原周期 lcm 的唯一时刻类；在题目长度内恰重复上述倍数。因此最终乘法恰覆盖全部时间，且不重复。

把 $q_i$ 写成 $gab,gac,gbc$ 并选择最小者后，扫描事件数为 $O(a+b)$，其中较大的 $a,b$ 仍不超过 $\sqrt{2\times10^{12}}$ 量级；其余运算为常数次 gcd/lcm。空间 $O(1)$（实现直接生成下一断点，不保存事件表）。

### 核心伪代码与参考实现附件

```text
p[i] = g[i] + r[i]
q[i] = lcm(gcd(p[i],p[j]), gcd(p[i],p[k]))
L = lcm(q[0],q[1],q[2])
reorder lights so q[0] is minimum

answer_one_period = 0
left = 0
while left < L:
    right = min(next change of w[1], next change of w[2], L)
    answer_one_period += w[1](left) * w[2](left)
                         * (prefix_w[0](right) - prefix_w[0](left))
    left = right

repeat = p[0]*p[1]*p[2] / lcm(p[0],p[1],p[2])
output answer_one_period * repeat modulo 998244353
```

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

### 实现细节、复盘与变式

- 原周期最多 $2\times10^{12}$；两数 lcm 即使最终只用于 gcd，也必须先进入 `__int128`。
- 当 `rem_i=0` 时该权重恒定，不应生成“周期起点与结束点重合”的重复事件。
- 用半开区间 $[l,r)$ 对应离散的整秒时刻，样例中的区间端点也按这一口径理解。
- 识别信号是“多个巨大周期，但相容性只比较 gcd 投影”；核心不是直接套 CRT，而是先问 CRT 实际读取了每个余数的哪些信息。
- 若灯数从 3 增大，压缩仍成立，但交叉方波断点可能无法通过“留下一个前缀和、扫描其余两个”控制；三变量是复杂度证明的重要边界。

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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