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

完整 C++17 附件

精选例题 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

完整 C++17 附件

精选例题 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

完整 C++17 附件

扩展与联系

高阶例题：Three Traffic Lights

来源信息与题意

VJudge：AtCoder-agc050_e Three Traffic Lights
原题：AtCoder Grand Contest 050 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$。

Hint 1：一秒对应三个余数

令周期 $p_i=g_i+r_i$。时刻 $t$ 绿当且仅当 $t\bmod p_i

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

余数 $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)). $$

Hint 3：压缩后一个余数有多少个绿色原像

对 $0\le x

Hint 4：不要枚举压缩后的总周期

令 $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$ 在一周期内只有一次从“商加一”降到“商”。选一个函数做区间求和，只扫描另外两个函数的变化时刻。

Observations

直接枚举时间的周期可能接近三个 $10^{12}$ 数的最小公倍数；直接枚举三组绿色余数更坏。非互质 CRT 的兼容条件只看两两 gcd，这允许先删除每个余数中永远不会被比较的素因子指数。
$q_i$ 不是随意取一个 gcd：它必须同时保留与另外两盏灯比较所需的两个模数，因此是这两个 gcd 的 lcm。更小会合并兼容性不同的余数，更大则没有新增判断信息。
压缩后的余数并非权重 1。同一个 $x\bmod q_i$ 在原绿色区间里可能有多个原像；整商 + 一个短前缀 精确保留了这些重数。
即使 $L$ 仍很大，$w_i$ 也只是周期方波。把一个方波前缀和公式化，乘积只需在另两个方波的断点间积分。
三个 $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，避免乘法溢出。

正确性证明

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

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

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

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

实现细节、复盘与变式

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

扩展与联系

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

总结与自检

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

课后训练建议

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

02-CRT与非互质同余合并.md 12 KB История Директен файл

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

本节目标

前置知识与课前自测

问题动机与核心推导

实现指南

精选例题 1：Biorhythms

来源与题意

Observations、Editorial 与证明

核心伪代码与附件

精选例题 2：Strange Way to Express Integers

来源与题意

Observations

Editorial 与正确性证明

核心伪代码与附件

精选例题 3：Throne

来源与题意

Observations、Editorial 与证明

核心伪代码与附件

扩展与联系

高阶例题：Three Traffic Lights

来源信息与题意

Observations

Editorial

正确性证明

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

实现细节、复盘与变式

扩展与联系

总结与自检

课后训练建议

02-CRT与非互质同余合并.md 12 KB

История Директен файл