6.9 KiB
一、思想
中国剩余定理(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) 。
步骤
-
前
i−1个方程，通解为x=r_1+q\cdot M,q∈Z。 -
在
q中找到某些特殊值t，使得(r_1+t∗M) \equiv r_2 (mod \ m_i) \Rightarrow M∗t+m_i∗y=r_2−r_1$,只有这样，合并完的方程才能满足第 $i个方程。 -
上式中
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),否则无解。 -
在判断有解的情况下，使用扩展欧几里得求出方程
ax+by=gcd(a,b)的一组特解x_0,y_0，同时求出d。 -
求出的是
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的一个特解。 -
合并后通解:
x=r_1+t∗M+p∗lcm(M,m_i),p∈Z依据：这里提到的【定理】 -
对通解模
lcm(M,m_i)即可得到新的ans作为前k个同余方程的最小整数解 -
更新
ans和M,让M成为前i个同余方程模数的最小公倍数。
实现细节
注意这里得用快速（龟速）乘，否则会爆long long ,而且 r_2−r_1 不能是负数（否则快速乘会 TLE ) , 所以这里都要使用一些取模的技巧。