（扩展）中国剩余定理

中国剩余定理（$\textbf{CRT}$）

解决问题类型

例题：洛谷 P1495 【模板】中国剩余定理（CRT）（本题需要使用 快速乘，否则超出 unsigned long long 的存储范围）。

给定 $n$ 个两两互质的正整数，构成序列 $\{m_n\}$。再给定序列 $\{a_n\}$，有如下同余方程
$$ \begin{cases} {x} \equiv {a_1} \pmod {m_1}\\ {x} \equiv {a_2} \pmod {m_2}\\ {x} \equiv {a_3} \pmod {m_3}\\ \cdots\\ {x} \equiv {a_n} \pmod {m_n}\\ \end{cases} $$
求 $x$ 的最小正整数解。

结论

令 $M=\prod_{i=1}^{n}m_i$，$M_i=\dfrac{M}{m_i}$。

然后考虑求出 $M_i\times p_i+m_i\times q_i=1$ 的一组可行解 $(p_i,q_i)$。

由于 $m_i$ 两两互质，所以 $M_i\perp m_i$，那么 $\gcd(M_i,m_i)=1$。

根据裴蜀定理，该方程必然存在解，故使用 $\text{Exgcd}$ 求解即可。

令 $e_i=M_i\times p_i$，则
$$ x=\bigg(\sum_{i=1}^{n}{e_1\times a_1}\bigg)\bmod M $$
这就是 $x$ 的最小正整数解。

证明

考虑 $e_{i}\times a_{i}$ 对 $m_j$ 取模的值，可以发现
$$ \begin{cases} e_i\times a_i \equiv 0 \pmod {m_j}&i\not=j&(1)\\ e_i\times a_i \equiv a_i \pmod {m_j}&i=j&(2)\\ \end{cases} $$

$(1)$ 式中，由于 $e_i=M_i\times p_i$，而 $M_i$ 是 $m_j$ 的倍数，所以结果为 $0$。

$(2)$ 式中，$p_i$ 和 $q_i$ 满足 $M_i\times p_i+m_i\times q_i=1$，等式两边对 $m_i$ 取模，即得 $e_i\bmod m_i=1$，再两边同乘 $a_i$ 就可以得证。

由此不难发现，将 $\sum_{i=1}^{n}e_i\times a_i$ 代入第 $i\,(i\in [1,n])$ 个同余式中，$e_j\times a_j\bmod m_i=0\,(i\not= j)$，对运算结果无影响，而 $e_i\times a_i\bmod m_i=a_i$，刚好统计下来。故 $\text{CRT}$ 得证。

算法流程

求出 $M=\prod_{i=1}^{n}{m_i}$。
求出 $M_i=\dfrac{M}{m_i}$。
用 $\text{Exgcd}$ 求出 $M_i\times p_i+m_i\times q_i=1$ 的 $p_i$。

注意，此时 $p_i$ 可能为负数，可以通过 $p_i\gets p_i+m_i$，$q_i\gets q_i-M_i$，将 $p_i$ 变为非负数。
通过公式

$$ x=\bigg(\sum\limits_{i=1}^{n}M_i\times p_i\times a_i\bigg)\bmod M $$

得到答案。

时间复杂度

时间复杂度为 $\Theta(n+n+n\log n+n)\approx O(n\log n)$，瓶颈在第三步求解不定方程。

$\textbf{Code}$

前置：

$\text{Exgcd}$ 中的 lint exgcd(lint, lint, lint &, lint &);。
快速乘中的 lint mul(lint, lint, lint);。

using lint = long long;
const int N = /*同余方程数量*/。

int n, a[N], m[N];
lint ans, p, q, M = 1, mm[N];

for (int i = 1; i <= n; ++i) M *= m[i];
for (int i = 1; i <= n; ++i) mm[i] = M / m[i];
for (int i = 1; i <= n; ++i) {
  exgcd(mm[i], m[i], p, q);
  ans = (ans + mul(mul(mm[i], p, M), a[i], M) % M + M) % M;
}

扩展中国剩余定理（$\textbf{ExCRT}$）

解决问题类型

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

给定序列 $\{m_n\}$ 和序列 $\{a_n\}$，有如下同余方程
$$ \begin{cases} {x} \equiv {a_1} \pmod {m_1}\\ {x} \equiv {a_2} \pmod {m_2}\\ {x} \equiv {a_3} \pmod {m_3}\\ \cdots\\ {x} \equiv {a_n} \pmod {m_n}\\ \end{cases} $$
求 $x$ 的最小正整数解。

两个方程

设方程为
$$ \begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2} \end{cases} \Rightarrow \begin{cases} x=m_1p+a_1\tag{1}\\ x=m_2q+a_2 \end{cases} $$
将两式联立，可得
$$ m_1p-m_2q=a_2-a_1 $$
可以使用扩展欧几里得算法求出 $p,q$ 的一组解 $p_0,q_0$。

令 $d=(m_1,m_2)$。

那么这个方程的全部解即为
$$ \begin{cases} p=p_0+\dfrac{m_2}{d}k\\ q=q_0+\dfrac{m_1}{d}k \end{cases} \hspace{1 cm}k\in \mathbb{Z} $$
将解代入 $(1)$ 中，可得
$$ \begin{aligned} x&=m_1\left(p_0+\dfrac{m2}{d}k\right)+a_1\\ &=m_1p_0+\dfrac{km_1m_2}{d}+a_1\\ &=m_1p_0+k[m_1,m_2]+a_1 \end{aligned} $$
令 $a'=m_1p_0+a_1$，$m'=[m_1,m_2]$，则 $x=a'+km'$，即
$$ x\equiv a'\pmod{m'} $$
这样就成功将两个方程合并为一个方程。