$exCrt$
前言
十几天前写的板子…然而当时就不会证以及打，只是抄了个板子，今天准备把坑填上。
$Description$
给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组
$$
\begin{cases}
x \equiv b_1\ ({\rm mod}\ a_1)
\\x \equiv b_2\ ({\rm mod}\ a_2)
\\\ldots
\\x\equiv b_n ({\rm mod}\ a_n)
\end{cases}
$$
的最小非负整数解。
$Solution$
先从简单的入手，现在有
$$
\begin{cases}
x \equiv b_1\ ({\rm mod}\ a_1)
\\x \equiv b_2\ ({\rm mod}\ a_2)
\end{cases}
$$
将其转换成
$$
\begin{cases}
x = b_1k_1
\\x = b_2k_2
\end{cases}
$$
联立一下，就有
$$
b1k1 = a_2 - a_1 + b_2k_2
$$
根据 $exgcd$ 可知，满足有解的条件是 $gcd (b_1, b_2) | (a_2 - a_1)$
设
$$
d = gcd(b_1, b_2)
$$
两边同除以 $d$ ，得
$$
\frac{b_1}{d}k_1 = \frac{a_2 - a_1}{d} + \frac{b_2}{d}k_2
$$
两边同时对 $\dfrac{b_2}{d}$ 取模，得
$$
\frac{b_1}{d}k_1 = \frac{a_2 - a_1}{d} \pmod { \frac{b_2}{d} }
$$
即
$$
k_1 \equiv (\frac{b_1}{d})^{-1} \times \frac{a_2 - a_1}{d} \pmod {\frac{b_2}{d}}
$$
也即
$$
k_1 = (\frac{b_1}{d})^{-1} \times \frac{a_2 - a_1}{d} + y\frac{b_2}{d}
$$
带回原式，得
$$
x = b_1 \times (\frac{b_1}{d})^{-1} \times \frac{a_2 - a_1}{d} + y\frac{b_1b_2}{d} + a_1
$$
即
$$
x = b_1 \times (\frac{b_1}{d})^{-1} \times \frac{a_2 - a_1}{d} + y\frac{b_1b_2}{d}
$$
设 $c = b_1 \times (\dfrac{b_1}{d})^{-1} \times \dfrac{a_2 - a_1}{d}, m = \dfrac{b_1b_2}{d}$
就做出了这个简单的式子。
然后我们考虑通解。
设已经求出前 $k - 1$ 个方程组成的同余方程组得解为 $Ans$ ， $M = \operatorname{LCM}_{i - 1}^{k - 1}a[i]$ 。
所以前 $k - 1$ 个方程的通解为 $Ans + i * M$ 。
然后我们考虑加入第 $k$ 个方程后的方程组，也就是要我们求
$$
Ans + Mx \equiv b_k \pmod {a_k}
$$
也就是求
$$
Mx \equiv b_k - Ans \pmod {a_k}
$$
即
$$
Mx + a_ky = b_k - Ans
$$
然后我们考虑用 $exgcd$ 求出 $t$ ，重复 $n$ 遍即可。
$Code:$
1 |
|