中国剩余定理
2026-07-29
定义
CRT 用来求解以下形式的一元线性同余方程组:
⎩⎨⎧x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)
中国剩余定理
CRT 要求所有 m 必须两两互质,我们设
P=i=1∏kmi,ri=miP
显然,ri 中包含除 mi 以外的两两互质的质数,即 gcd(ri,mi)=1,即 ri 在模 mi 意义下有逆元。
考虑构造 yi≡ai⋅ri−1(modmi),则 xi=yi⋅ri。
则 xi 模 mi 为 ai,模其他 mj 都为 0,我们对于每个 i 都这么构造,最终所有的叠加起来即为原方程组一个解,我们将所有 xi 相加:
x=i=1∑kxi≡i=1∑kai⋅ri⋅ri−1(modP)
注意:这里的 ri−1 是在其对应的 mi 下的逆元。
LL M = 1;
for(int i = 1 ; i <= n ; i ++) M *= m[i];
for(int i = 1 ; i <= n ; i ++) {
LL Mi = M / m[i] , ti = inv(Mi%m[i] , m[i]);
ans = (ans + (int128) a[i] * Mi % M * ti % M) % M;
}扩展中国剩余定理
与 CRT 不同,由于每个 m 不能保证两两互质,我们考虑合并同余方程,比如我们要合并
x≡a1(modm1)
和
x≡a2(modm2)
只需要将 x=a1+m1⋅k 带入第二个方程:
m1⋅k≡a2−a1(modm2)
这样就转换成了一次同余方程,取 g=gcd(m1,m2):
- 若 g∤(a2−a1),原方程无解。
- 否则考虑解出 m1⋅x+m2⋅y=g 的特解 x0,由于 g∣(a2−a1),两边同乘 ga2−a1 得到特解 k0,我们直接,新余数为 a1+m1⋅k,新模数为 lcm(m1,m2)=gm1⋅m2。
不断把新方程合并,就能得到最终结果。
LL M = 1 , ans = 0;
for(int i = 1 ; i <= n ; i ++) {
LL x , y; LL g = exgcd(M , m[i] , x , y);
LL nM = M / g * m[i];
ans = (ans + (int128) (((int128(a[i]-ans)/g * x % (m[i]/g)) + m[i]/g) % (m[i]/g)) * M % nM) % nM;
M = nM;
}