学习系列 —— 中国剩余定理（Chinese Remainder Theorem） - Problem

《九章算术》中曾经提到过一个经典的问题

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

翻译一下就是：已知一个正整数模 $3$ 余 $2$，模 $5$ 余 $3$，模 $7$ 余 $2$，求这个数是几？
写成数学语言就是求解同余方程组。
$\begin{cases}
x \equiv 2\ (\bmod 3)\\
x \equiv 3\ (\bmod 5)\\
x \equiv 2\ (\bmod 7)\\
\end{cases}$

中国剩余定理 (Chinese Remainder Theorem，CRT) 可求解如下形式的一元线性同余方程组（其中 $a_1,a_2,\cdots,a_k$ 两两互质）：
$\begin{cases}
x \equiv b_1\ (\bmod a_1)\\
x \equiv b_2\ (\bmod a_2)\\
...\\
x \equiv b_k\ (\bmod a_k)\\
\end{cases}$
的核心是找到一列数 $b_1,b_2,…,b_k$ 使得
$\begin{cases}
b_1 \equiv 1\ (\bmod a_1)\\
b_1 \equiv 0\ (\bmod a_2)\\
...\\
b_1 \equiv 0\ (\bmod a_k)\\
\end{cases},\
\begin{cases}
b_2 \equiv 0\ (\bmod a_1)\\
b_2 \equiv 1\ (\bmod a_2)\\
...\\
b_2 \equiv 0\ (\bmod a_k)\\
\end{cases}, \cdots,\
\begin{cases}
b_k \equiv 0\ (\bmod a_1)\\
b_k \equiv 0\ (\bmod a_2)\\
...\\
b_k \equiv 1\ (\bmod a_k)\\
\end{cases}$
哪么 $x=m_1b_1+m_2b_2+\cdots+m_kb_k$ 就是原方程组的一个解。
设 $M_i = \prod_{i=1}^n {m_i}$，并设 $M_i = \frac{M}{m_i},\ t_i=M_{i}^{-1}$ 为 $M_i$ 在模 $m_i$ 的意义下的乘法逆元，那么 $b_i = M_i \times t_i$，由此可以得到方程在模 $M$ 意义下的唯一解：
$x=\left(\sum_{i=1}^n a_it_iM_i\right)\bmod M$

中国剩余定理中有一个重要步骤就是用扩展欧几里得算法求解裴蜀等式的系数。

扩展中国剩余定理，和中国剩余定理相比，没有保证模数两两互质。
了解扩展中国剩余定理，难的是数学过程推导。
这个推导对于我们理解代码是至关重要的。
首先，我们定义一下推导过程中的符号。
1. $a_i$ 为扩展中国剩余定理中的模数。
2. $b_i$ 为扩展中国剩余定理中的余数。
我们先从第 $1$ 和第 $2$ 个方程开始推导。根据定理可得
$\begin{cases} b_1\ (\bmod a_1) \equiv x \\\\ b_2\ (\bmod a_2) \equiv x\end{cases} \to \begin{cases} a_1 \times x_1+b_1=x \\\\ a_2 \times x_2+b_2= x\end{cases} \to a_1 \times x_1+b_1=a_2 \times x_2+b_2 \to\\\\ a_1 \times x_1-a_2 \times x_2=b_2-b_1 \to\\\\ a_1 \times x+a_2 \times y=b_2-b_1$
这样，我们熟悉的扩展欧几里得算法就出现了。利用扩欧，我们可以计算出对应的 $x,y$。
设 $d$ 为扩欧算法计算出的最大公约数。如果 $d$ 不能整除 $b_2-b_1$，则方程无解。
如果方程有解。记 $y_1=(b_2-b_1)/d$，我们只需要将 $x$ 扩展 $y_1$ 倍，就可以找到一个新的方程，该方程将继续满足中国剩余定理。我们可以将第 $1$ 和第 $2$ 方程合并称为一个新的方程 $a_1^{\prime} \times x^{\prime}+b_1^{\prime}=x$。
记 $t=|a_2/d|$。
这样 $x \to x \times (b_2-b_1)/d \to (x\%t+t)\% t$。
有了新的 $x$，我们可以利用原式计算出新的 $b_1$，即 $b_1=a_1 \times x+b_1$。
有了新的 $b_1$，我们又可以计算出新的 $a_1$，即 $a_1=a_1/d \times a_2$。
这样崭新的 $a_1^{\prime} \times x^{\prime}+b_1^{\prime}=x$ 就诞生了，也就是将原来的第 $1$ 和第 $2$ 个方程合并为一个新方程。
这样，我们继续迭代第 $3$，第 $4$，$...$，第 $n$ 个方程。
最终的解就是 $(b_1\%a_1+a_1)\%a_1$。

【模板代码】

LL a[N];//模数 
LL b[N];//余数 
LL excrt(LL n) {
	LL a1=a[1], b1=b[1];
	LL x,y;
	for (LL i=2; i<=n; i++) {
		LL d=exgcd(a1, a[i], x, y);
		if ((b[i]-b1)%d) {
			return -1;
		}
		x*=(b[i]-b1)/d;
		LL t=abs(a[i]/d);
		x=(x%t+t)%t;
		b1=x*a1+b1;
		a1=(a1/d*a[i]);
	}
	return (b1%a1+a1)%a1;
}

ans 即为方程解，其中 -1 表示无解。

6483: 学习系列 —— 中国剩余定理（Chinese Remainder Theorem）

Description

Source/Category