|
|
## 一、思想
|
|
|
中国剩余定理($CRT$)**不能解决模数不互质情况的模线性同余方程组**。
|
|
|
|
|
|
方程组是由很多个模线性同余方程构成的。假设我们能把两个模线性同余方程组，等价地合并成一个方程，问题就迎刃而解了——只需要不停地合并这些方程，只到只剩下一个。
|
|
|
|
|
|
理想是美好的，道路是曲折的。首先，未必两个方程可以合并成一个方程（我们可能找不到快速的实现方式）。此外，即使可以把两个方程合并成一个，这个变换也未必是等价变换（可能新方程的解未必是原方程的解，也可能原方程的解被新方程漏掉了）。我们要做的事情是：给出将两个方程合并成一个方程的方法，然后证明这个变换的等价性。
|
|
|
|
|
|
---
|
|
|
### 二、数学基础
|
|
|
作为我们接下来讨论的基础，我想先展示几个例子。它们的规模都很小，完全可以手工验证。
|
|
|
$$ \large
|
|
|
\left\{\begin{matrix}
|
|
|
x \equiv 2(mod \ 4) \\
|
|
|
x \equiv 4(mod \ 6) \\
|
|
|
\end{matrix}\right. \Rightarrow x \equiv 10 (mod \ 12)
|
|
|
$$
|
|
|
|
|
|
由$(1)$式，手动模拟一些$x$,得：$6, 10,14,18,22,26,30,34,38,42,46...$
|
|
|
|
|
|
由$(2)$式，手动模拟一些$x$,得：$10,16,22,28,34,40,46,52,58...$
|
|
|
|
|
|
可以发现，这两个式子要想得到的公共解，其实是一组解，它们是：$\large 10,22,34,46,...$
|
|
|
|
|
|
找一下规律，就是从$\large 10$开始，循环节为$\large 12$，也就是原来两个模数$\large 4,6$的$\large [4,6]$。
|
|
|
|
|
|
---
|
|
|
|
|
|
$$ \large
|
|
|
\left\{\begin{matrix}
|
|
|
x \equiv 4(mod \ 6) \\
|
|
|
x \equiv 3(mod \ 5) \\
|
|
|
\end{matrix}\right. \Rightarrow x \equiv 28 (mod \ 30)
|
|
|
$$
|
|
|
|
|
|
$\large (1): 10,16,22,28,34,40,46,52,58,64,70,76,...$
|
|
|
$\large (2): 8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,...$
|
|
|
|
|
|
总结规律：循环节是$30$,最小起点是$28$
|
|
|
|
|
|
---
|
|
|
|
|
|
$$ \large
|
|
|
\left\{\begin{matrix}
|
|
|
x \equiv 2(mod \ 4) \\
|
|
|
x \equiv 3(mod \ 6) \\
|
|
|
\end{matrix}\right. \Rightarrow ∅
|
|
|
$$
|
|
|
|
|
|
$\large (1):2,6,10,14,18,22,26,30,34,38,42,....$
|
|
|
$\large (2):3,9,15,21,27,33,39,...$
|
|
|
可以发现，两者完美错过(~~一个是奇数序列，一个是偶数序列，怎么相交？~~),今生无缘~
|
|
|
|
|
|
---
|
|
|
可以粗略地总结出几个规律：
|
|
|
|
|
|
* 新方程与原方程具有同样的形式。
|
|
|
* 新方程的模数，是之前两个模数的$lcm$。
|
|
|
* 可能存在无解的情况
|
|
|
|
|
|
这几条性质是整个算法的基石，我们会在后文详细讨论。这里先一步步摸出 “合并” 的算法。形式化地，考虑这样一组模线性同余方程：
|
|
|
$$\left\{\begin{matrix}
|
|
|
a \equiv r_1 \ (mod \ m_1) \\
|
|
|
a \equiv r_2 \ (mod \ m_2)
|
|
|
\end{matrix}\right.
|
|
|
$$
|
|
|
|
|
|
这个方程组等价于：
|
|
|
$$\large a=k_1m_1+r_1=k_2m_2+r_2$$
|
|
|
|
|
|
移一下项，立刻有
|
|
|
$$\large k_1m_1-k_2m_2=r_2-r_1$$
|
|
|
|
|
|
左边的$m_1,m_2$,右边的$r_2-r_1$是已知量。这就是一个典型的不定方程。解不定方程这个任务，我们是熟悉的：可以通过裴蜀定理判断有没有解，可以用扩展欧几里得算法($exgcd$)给出$k_1,k_2$的整个解系。于是算法有了第一步：
|
|
|
|
|
|
* 如果$gcd(m_1,m_2)|(r_2-r_1)$,则判断方程有解
|
|
|
* 否则，报告无解
|
|
|
|
|
|
接下来考虑如何求出一组 $k_1, k_2$约定几个记号：记$d=gcd(m_1,m_2)$,$p_1=\frac{m_1}{d},p_2=\frac{m_2}{d}$,显然$p_1,p_2$是互质的。那么把$m_1$用$p_1d$来代替，$m_2$用$p_2d$来代替,可以把上面的式子写成：
|
|
|
$$\large k_1p_1-k_2p_2=\frac{r_2-r_1}{d}$$
|
|
|
|
|
|
右边那一串东西是整数，因为当且仅当 $d | (r_2-r_1)$才会有解。**左边满足了$gcd(p_1,p_2)$互质**，因此求出整体解系是很容易的。现在假设我们拿$exgcd$求出了下面这个方程的**特解**($λ_1,λ_2$):
|
|
|
$$\large λ_1p_1+λ_2p_2=1$$
|
|
|
|
|
|
这是一个非常标准的$exgcd$. 求出来了$λ_1,λ_2$之后，可以直接拼出$k_1,k_2$(就是翻整数倍、加上负号等操作):
|
|
|
$$
|
|
|
\large \left\{\begin{matrix}
|
|
|
k_1=\frac{r_2-r_1}{d}λ_1 \\
|
|
|
k_2=-\frac{r_2-r_1}{d}λ_2
|
|
|
\end{matrix}\right.
|
|
|
$$
|
|
|
于是：
|
|
|
$$\large x=r_1+k_1m_1=r_1+\frac{r2-r1}{d}λ_1m_1$$
|
|
|
|
|
|
至此，我们成功地构造出了一个 $x$，满足
|
|
|
$$
|
|
|
\large \left\{\begin{matrix}
|
|
|
x \equiv r_1 \ (mod \ m_1) \\
|
|
|
x \equiv r_2 \ (mod \ m_2)
|
|
|
\end{matrix}\right.
|
|
|
$$
|
|
|
|
|
|
* $r_1,\frac{r2-r1}{d}$是常数，$λ_1$通过$exgcd$可以计算出来，这不就是一个$x=r_1+k'm_1$吗~
|
|
|
* 也就是通过一顿操作，把两个方程等式合并为一个方程等式~
|
|
|
|
|
|
但是整个解系如何给出呢？我们有:
|
|
|
**【定理】**
|
|
|
若方程组
|
|
|
$$
|
|
|
\large \left\{\begin{matrix}
|
|
|
x \equiv r_1 \ (mod \ m_1) \\
|
|
|
x \equiv r_2 \ (mod \ m_2)
|
|
|
\end{matrix}\right.
|
|
|
$$
|
|
|
有特解$x^{'}$,那么通解是：$x^{'}+k\cdot lcm(m_1,m_2)$,亦即
|
|
|
$$\large x \equiv x^{'} \ (mod \ lcm(m_1,m_2)) $$
|
|
|
|
|
|
这里就不进行数学证明了，联想一下最上面的两个式子:
|
|
|
|
|
|
$$ \large
|
|
|
\left\{\begin{matrix}
|
|
|
x \equiv 2(mod \ 4) \\
|
|
|
x \equiv 4(mod \ 6) \\
|
|
|
\end{matrix}\right. \Rightarrow x \equiv 10 (mod \ 12)
|
|
|
$$
|
|
|
|
|
|
|
|
|
参考博客：https://www.cnblogs.com/ailanxier/p/13370753.html
|
|
|
|
|
|
### 合并流程
|
|
|
假设前 $i−1$ 个同余方程合并得到的新方程为：$x \equiv r_1(mod \ M)$, $M$ 是前 $i−1$ 个同余方程模数的**最小公倍数**，现在考虑合并第 $i$ 个方程：$x \equiv r_2(mod \ m_i)$ 。
|
|
|
|
|
|
#### 步骤
|
|
|
1. 前 $i−1$ 个方程，通解为 $x=r_1+q\cdot M,q∈Z$。
|
|
|
<br>
|
|
|
2. 在$q$中找到某些特殊值$t$ ，使得 $$(r_1+t∗M) \equiv r_2 (mod \ m_i) \Rightarrow M∗t+m_i∗y=r_2−r_1$$ ,只有这样，合并完的方程才能满足第 $i$个方程。
|
|
|
<br>
|
|
|
3. 上式中$t,y$是未知的，其它是已知的常数，这就是标准的形如$ax+by=c$的二元一次不定方程，可以用**裴蜀定理**来判断是否有解：
|
|
|
$M$ 就是 $a$ , $t$ 就是 $x$ ,$m_i$就是$b$,$c$就是$r_2-r_1$。
|
|
|
设$d=gcd(M,m_i)$,则 $r_2−r_1$ 要满足 $d|(r_2−r_1)$ ,否则无解。
|
|
|
<br>
|
|
|
|
|
|
4. 在判断有解的情况下，使用**扩展欧几里得**求出方程$ax+by=gcd(a,b)$的一组特解$x_0,y_0$，同时求出 $d$。
|
|
|
<br>
|
|
|
|
|
|
5. 求出的是$ax+by=gcd(a,b)$的解，并不是$ax+by=c$的解，所以，为了拿到$ax+by=c$的一组解，需要把$x_0*\frac{c}{d}$才能得到一个有用的解。 $\large x=x_0∗ \frac{r_2−r_1}{d}$ ,得到方程$M∗t+m_i∗y=r_2−r_1$的一个特解。
|
|
|
<br>
|
|
|
|
|
|
6. 合并后通解: $x=r_1+t∗M+p∗lcm(M,m_i),p∈Z$
|
|
|
依据：这里提到的[【定理】](https://www.luogu.com.cn/blog/blue/kuo-zhan-zhong-guo-sheng-yu-ding-li )
|
|
|
<br>
|
|
|
7. 对通解模 $lcm(M,m_i)$ 即可得到新的 $ans$ 作为前 $k$ 个同余方程的**最小整数解**
|
|
|
<br>
|
|
|
|
|
|
8. 更新 $ans$ 和 $M$ ,让 $M$ 成为前 $i$ 个同余方程模数的最小公倍数。
|
|
|
<br>
|
|
|
|
|
|
#### 实现细节
|
|
|
|
|
|
注意这里得用快速（龟速）乘，否则会爆$long$ $long$ ,而且 $r_2−r_1$ 不能是负数（否则快速乘会 $TLE$ ) , 所以这里都要使用一些取模的技巧。
|
|
|
|
