中国剩余定理

参考资料

• 中国剩余定理 - OI Wiki

简介

中国剩余定理 (Chinese Remainder Theorem，CRT) 可求解如下形式的一元线性同余方程组：

$$\begin{cases} x & \equiv a_1\pmod{n_1} \\ x & \equiv a_2\pmod{n_2} \\ & \vdots \\ x & \equiv a_k\pmod{n_k} \end{cases}$$

其中 $n_1,n_2,\dots,n_k$ 两两互质。

扩展中国剩余定理（EXCRT）可以解决模数不互质的情况。

例题

洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

给定 $n$ 组同余方程 $x\equiv a_i\pmod{b_i}$（$b_i$ 两两互质），求满足所有方程的最小非负整数 $x$。

洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

给定 $n$ 组非负整数 $a_i, b_i$，求解关于 $x$ 的方程组的最小非负整数解。

$$\begin{cases} x\equiv b_1\pmod{a_1} \\ x\equiv b_2\pmod{a_2} \\ \dots \\ x\equiv b_n\pmod{a_n} \end{cases}$$