02-CRT与非互质同余合并.md 5.2 KB
CRT：从互质公式到非互质同余合并
本节目标
能用中国剩余定理（Chinese Remainder Theorem, CRT）合并互质同余，用扩展 CRT（exCRT）处理非互质模数，判断无解并控制乘法溢出。
前置知识与课前自测
前置：gcd、扩展欧几里得、模逆、线性同余。
- 方程 $ax\equiv b\pmod m$ 何时有解？
- 两同余模数不互质时，余数必须满足什么兼容条件？
- 合并后新模数一定是两模数乘积吗？
答案
1. 当且仅当 $\gcd(a,m)\mid b$。 2. 两余数之差能被模数 gcd 整除。 3. 不是，最小周期是 lcm；互质时才等于乘积。问题动机与核心推导
已合并为
$$ 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，East Central North America 1999
- 三个周期分别为 23、28、33，已知各自峰值余数及当前天 d，求 d 之后下一次三峰同日还要多少天。
Hint 1
求 $x\equiv p(23),e(28),i(33)$。Hint 2
三模数互质，总周期 21252；求得余数后换成严格大于 d 的代表。Observations、Editorial 与证明
互质 CRT 给出模 21252 的唯一解类。合并余数 r 后，答案是 (r-d) mod 21252，若结果为 0 则取 21252，因为题目要求未来而非当天。CRT 唯一性保证该正代表是下一次而非某次更晚相遇。
核心伪代码与附件
r, period = CRT([(p,23), (e,28), (i,33)])
days = (r - d) mod period
if days == 0: days = period
精选例题 2：Strange Way to Express Integers
来源与题意
- POJ-2891 Strange Way to Express Integers，POJ Monthly 2006
- 多组直到 EOF；给若干
x ≡ remainder (mod modulus)，模数不保证互质，求最小非负解或 -1。
Hint 1
维护当前 `(r,M)`，逐条调用上面的线性同余合并。Hint 2
兼容条件是 `(b-r)%g==0`。Observations
- 不能先把模数相乘：非互质会重复周期因子，也可能掩盖矛盾。
- 每次合并后的
(r,M)完整代表此前所有方程，不需保存旧式子。 - 无解一旦出现，后续约束不可能修复。
Editorial 与正确性证明
初始 (0,1) 表示所有整数。逐条代入 x=r+Mt 解线性同余；若兼容则得到所有共同解的唯一剩余类，更新为规范化的 (r,lcm)。归纳可知处理 k 条后恰表示前 k 条共同解集；最终 r 是最小非负解。每次 $O(\log\max modulus)$。
核心伪代码与附件
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
精选例题 3：Throne
来源与题意
- AtCoder-abc186_e Throne
- 多组给 $N,S,K$，求最小非负 x 使
(S+Kx) mod N = 0，无解输出 -1。
Hint 1
改写为 $Kx\equiv-S\pmod N$。Hint 2
先除以 $g=\gcd(K,N)$，再求逆元。Observations、Editorial 与证明
线性同余有解当且仅当 g 整除 S。约分后 K/g 与 N/g 互质，其逆元存在；乘到右侧并规范化就得到模 N/g 的唯一解类，最小非负代表即答案。每组 $O(\log N)$。
核心伪代码与附件
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
扩展与联系
CRT 解决的是多个同一未知量的同余交集；高斯消元解决多个未知量的线性系统。模数不是质数时，多变量系统可考虑质因数分解后分别求解再 CRT，但素数幂上的消元仍需处理非单位主元。
总结与自检
- exCRT 的兼容条件从哪里来？
- 新周期为何是 lcm？
- 严格未来查询为何把 0 改成整周期？
- 线性同余约 gcd 后为什么可以求逆？
课后训练建议
枚举小模数所有 x 对拍 exCRT，覆盖兼容非互质、不兼容、某模数整除另一模数。用接近 $10^{18}$ 的数检查中间乘法是否需要 128 位。