中国剩余定理

概述

中国剩余定理用于求解模数两两互质的一元线性同余方程组，通过构造与各模数互补的系数，把方程组的余数组合成模所有模数之积意义下的唯一解。当模数不互质时标准构造失效，改用扩展中国剩余定理：将方程两两合并，每次借助扩展欧几里得算法求解线性同余，若无整数解则判定整个方程组无解。两道例题分别对应互质的标准版本与需要逐步合并的扩展版本。

参考资料

• 中国剩余定理 - 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}$$