中国剩余定理笔记【CRT】【exCRT】
中国剩余定理笔记【CRT】【exCRT】约定
设 \(\operatorname{inv}(x,p)\) 表示 \(x\) 在模 \(p\) 意义下的逆元。
中国剩余问题
给定一个关于 \(x\) 的方程组：
\[\begin{cases}x \equiv b_1\ (\operatorname{mod} a_1)\\x \equiv b_2\ (\operatorname{mod} a_2)\\\cdots\\x \equiv b_n\ (\operatorname{mod} a_n)\end{cases}\]
（其中 \(\forall a_i,b_i\)，有 \(0\leq b_i < a_i\)；\(\forall i\neq j\)，有 \(a_i\bot a_j\)。）
求 \(x\) 的解集。
构造的解法
这里我们使用类似于 lagrange 插值的思路，尝试构造出 \(x\) 的一组解。
首先，\(\forall 1\leq i\leq n\)，我们构造出 \(t_i\) 使得：
\
不妨设 \(A = \prod a_i\)，那么可以构造：
\
因为 \(a_i\) 两两互质，所以 \(\displaystyle\operatorname{inv}(\frac{A}{a_i},a_i)\) 是存在的。
然后，就可以构造 \(x_0 = \sum t_i\) 了。
我们发现，除了 \(x_0\) 是方程的一个解以外，\(x_0 + kA\)（\(k\in \mathbb{Z}\)）也是方程的解。那么，它是不是通解呢？（答案是肯定的）如果继续阅读本文，你就能找到答案。
这里，贴一下结论：
令 \(A=\prod a_i\)，方程的通解为：
\
（其中 \(k\in\mathbb{Z}\)）
直接计算，时间复杂度为 \(O(n\log V)\)，其中 \(V\) 为 \(a_i\) 的值域大小，\(O(\log V)\) 是求逆元导致的。
需要注意的是，需要存储的最大的整数是 \(A\)，它有可能非常大。
扩展中国剩余问题
给定一个关于 \(x\) 的方程组：
\[\begin{cases}x \equiv b_1\ (\operatorname{mod} a_1)\\x \equiv b_2\ (\operatorname{mod} a_2)\\\cdots\\x \equiv b_n\ (\operatorname{mod} a_n)\end{cases}\]
（其中 \(\forall a_i,b_i\)，有 \(0\leq b_i < a_i\)）
求 \(x\) 的解集。
注意：这与上一题的不同之处在于，缺少了 \(a_i\) 两两互质的条件。
合并方程的解法
这是 OI 界的主流解法。
这种解发基于一个观察，就是一下方程组：
\[\begin{cases}x \equiv b_1\ (\operatorname{mod} a_1)\\x \equiv b_2\ (\operatorname{mod} a_2)\end{cases}\]
可以被合并为一个等价的方程：
\
接下来我们将证明其可行性并找到方法。
首先，仍然考虑方程组
\[\begin{cases}x \equiv b_1\ (\operatorname{mod} a_1)\\x \equiv b_2\ (\operatorname{mod} a_2)\end{cases}\]
我们设未知数 \(k_1,k_2\)，然后将方程组写成带余除法的形式：
\
当然，根据带余除法的定义，\(k_1,k_2\) 均得是整数。
为了保留式子的对称性，我们先考虑方程 \(a_1 k_2 + b_1 = a_2 k_2 + b_2\)，将其移项得：
\
不妨设 \(d = \gcd(a_1, a_2)\)，因为 \(x\) 有解的充要条件是 \(k_1,k_2\) 有解，而根据 Bezout 定理，\(k_1,k_2\) 有解必须有 \(b_2 - b_1 | d\)，这样就可以直接判断无解情况了。
为了解出 \(k_1,k_2\)，我们先使用扩展欧几里得法解出方程（关于 \(x_1,x_2\) 的）：
\[\frac{a_1}{d} \cdot x_1 + \frac{a_2}{d} \cdot x_2 = 1\]
这里不妨设 \(x_1\) 的通解为 \(\displaystyle x_0 + t\cdot \frac{a_2}{d}\)（\(t\in\mathbb{Z}\)），则 \(k_1\) 的通解应该为：
\
（这是由 Bezout 定理的推论得出的）
然后将将 \(k_1\) 带入 \(x = a_1 k_1 + b_1\) 可得：
\
发现等号右边只有 \(t\in \mathbb{Z}\)，这很像带余除法的形式，而 \(\displaystyle \frac{a_1\cdot a_2}{d} = \operatorname{lcm}(a_1,a_2)\)，所以写成取模的形式，为：
\
然后就完成了合并。
这里总结一下合并的流程：
对于方程组：
\[\begin{cases} x \equiv b_1\ (\operatorname{mod} a_1)\\ x \equiv b_2\ (\operatorname{mod} a_2) \end{cases}\]
首先，判断是否 \(b_2 - b_1|\gcd(a_1,a_2)\)，如果不满足，则无解。
然后，解关于 \(x_1,x_2\) 的方程：
\[\frac{a_1}{\gcd(a_1,a_2)}\cdot x_1 + \frac{a_2}{\gcd(a_1, a_2)}\cdot x_2 = 1\]
获得 \(x_1\) 的一个特解 \(x_0\)，然后就可以得到结果：
\
那么，扩展欧几里得问题就可以通过不断合并来求解。
最后合并的结果应该是：
\
所以通解为 \(x = x' + t \cdot\overset{n}{\underset{i = 1}{\operatorname{lcm}}}\ a_i\)（\(t\in \mathbb Z\)）。
最终复杂度为 \(O(n\log V)\)。
分解质因数的解法
这个方法不常用，需要用到一个引理：
若 \(a\) 的质因数分解为 \(a = p_1 ^ {\alpha_1} p_2 ^ {\alpha_2} \cdots p_k ^ {\alpha_k}\)，那么关于 \(x\) 的方程：
\
等价于：
\[\begin{cases}x\equiv b\ (\operatorname{mod} p_1 ^ {\alpha_1})\\ x\equiv b\ (\operatorname{mod} p_2 ^ {\alpha_2})\\ \cdots\\ x\equiv b\ (\operatorname{mod} p_k ^ {\alpha_k})\end{cases}\]
把同余式写成整除式即可证明引理。
有了这个引理，我们只需把 \(a_i\) 全都质因子分解，就可以套用中国剩余定理的做法了。
如果使用 \(O(\sqrt V)\) 的暴力质因子分解，那么总时间复杂度为 \(O(n\sqrt V + n\log ^ 2 V)\)；如果使用 Pollard Pho 质因子分解，那么复杂度为 \(O(nV ^ {\frac{1}{4}} + n\log ^ 2 V)\)。
其他解法
实际上，解法可能更多，因为你用 exgcd 瞎代入消元都能做。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]