拓展CRT算法

拓展CRT算法

CRT算法（中国剩余算法）主要用于解决除法操作之后存在余数方程组的问题。CRT算法中除数之间互质，基于此性质，可以方便组织出解的形式。但是拓展CRT算法取消了该性质，故此不得不对方程中的各个算式逐一处理。

已知除数序列$d[]$ 和 余数序列$r[]$，计算最小的符合条件的$x$。其中，除数序列中各个数值未必互质。已知三者存在如下方程组规则：
KaTeX parse error: No such environment: align at position 16: \left\{ \begin{̲a̲l̲i̲g̲n̲}̲ x &= r_1\ \ (…
拓展CRT算法的主要思路是：对方程组中的每个算式依次合并，最终合并为一个算式$x=r^{\prime }(mod{d}^{\prime })$，最后通过该算式计算符合条件的最小值。

合并两个算式

先合并前两个算式。记系数为$k_i$，由前两个算式可以表示为：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ x &= k_1\cdot…
由于该算法的主要思路就是进行算式合并，故引用当前例子描述合并的行为。先合并以上两个式子有

​ $k_1\cdot d_1-k_2\cdot d_2=r_2-r1=k\cdot gcd(d_1,d_2)$

对当前的化简式子进行分析：

1. 无解情况。若$r_2-r_1$不能整除$gcd(d_1,d_2)$，显然无解；
2. 使用拓展欧几里得算法计算系数$k_1、k_2$。
   此时若对得到的$k_1$扩大$\frac{r_2-r_1}{gcd(d_1,d_2)}$倍，即可得到算式中真实的$k_1$值；
3. 此时得到了$k_1$的一个特值，记为$k_1^{{}^{\prime }}$；
4. 系数通项。又由于两个方程的限定关系，可以描述系数的通项；

通过两个方程分析得到的特值和推导关系可以得到系数$k_1$的通项 。若已知通项，代入其中一个式子中，则可以将两个式子合并为一个；

计算系数通项

先贴出系数通项的结果：
KaTeX parse error: No such environment: align at position 16: \left\{ \begin{̲a̲l̲i̲g̲n̲}̲ k_1 &= k'_1 + …
对其中的变量进行分析。

1. 变量$k_1$是由拓展欧几里得算法计算出的最小特值；
2. 变量$\frac{d_2}{gcd(d_1,d_2)}$表示$k_1$ 的最小步长，即两个相邻数值的差。该算式用于表示$k_1$的所有可能数值。
   之所以是$\frac{d_2}{gcd(d_1,d_2)}$，是因为两个算式使用同一个k，则$k_1$必须使用$d_2$表示步长，但是$d_2$ 并非最小步长，而使用$gcd$ 修正之后，$\frac{d_2}{gcd(d_1,d_2)}$ 和 $\frac{d_1}{gcd(d_1,d_2)}$互质。此时分母乘以任何大于1的数都满足不能整除，至此得到$k_1$的最小步长；

综上，得到系数的通项。代入$x=k_1\cdot d_1+r_1$中可以得到：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ x &= (k'_1 + k…
至此便化成了一个式子。如此化简下去，最终可以得到一个算式。

最终结果

从算式$x=k\times d^{\prime }+r^{\prime }$可以计算符合条件的最小x为：

• $x=(x+d^{\prime })\%d^{\prime }$

思路分析

解决该题目，首先需要有如下几个意识：

1. 两两合并。方程组中的方程需要两两合并，才可以解；
2. ！！！除余方程可解。最终合并生成的表示x的除余方程，可以分析出x的取值通项，可解；
3. 拓展欧几里得算法未必真实值。题中显然需要对其进行放缩，放大$\frac{r_2-r_1}{gcd}$倍；
4. 系数描述需要使用最小步长。题中互质的最小步长描述为 $\frac{d_1}{gcd}$ 和 $\frac{d_2}{gcd}$ ；
5. 除余方程可以计算满足条件的最小值。由算式$x=(x+d^{\prime })\%d^{\prime }$计算得到；

妥