CRT 与 exCRT

感觉网上很多写的都不是很清楚啊 awa。

CRT

就是解这个方程 \(\begin{cases}x\equiv r_1 \pmod {m_1}\\ x\equiv r_2 \pmod {m_2} \\\dots\\x_n \equiv r_n \pmod {m_n}\end{cases}\)，其中 \(m_1\sim m_n\) 两两互质，求 \(x\) 最小解。

令 \(M = \prod\limits_{i = 1}^n m_i\)，\(t_i\) 为 \(\dfrac{M}{m_i}\) 在模 \(m_i\) 意义下的乘法逆元。。则有 \(ans_0 = \sum\limits_{i = 1}^n \dfrac{M}{m_i} t_i r_i\)，通解形式为 \(ans = ans_0 + kM\)，特别的其中小于 \(M\) 的非负整数解只有一个，那就是 \(ans = ans_0\bmod M\)，这也是最小解。

证明：先证明正确性，再证明唯一性。

正确性：（感觉很显然 qwq）对于任意 \(1\le k \le n\) 有 \(\sum\limits_{i = 1}^n \dfrac{M}{m_i}t_i r_i \equiv r_k\pmod {m_k}\)。对于 \(i\not= k\) 时，\(\dfrac{M}{m_i} \equiv 0\pmod {m_k}\)（显然），这个时候不会对 \(\sum\limits_{i = 1}^n \dfrac{M}{m_i} t_i r_i\) 这个式子做出任何贡献。当 \(i = k\) 时，由于 \(t_i\) 是 \(\dfrac{M}{m_i}\) 在堆 \(m_i\) 取余意义下的逆元，因此 \(\dfrac{M}{m_i}t_i\equiv 1\pmod {m_i}\)。因为这里 \(i = k\)，所以应该是 \(\dfrac{M}{m_k}t_k\equiv 1\pmod{m_k}\)，两边同乘一个 \(r_k\) 就得到了 \(\dfrac{M}{m_k}t_k r_k\equiv r_k\pmod {m_k}\)。因此就有 \(\sum\limits_{i = 1}^n \dfrac{M}{m_i}t_i r_i \equiv r_k\pmod {m_k}\)。

唯一性。这里唯一性是指小于 \(M\) 的解唯一。假设我们已经找到了一个解 \(x\)，它的通解形式显然是 \(x + kM\)，可以用反证法证明。那么只要 \(k \not= 1\) 则 \(x + kM> M\)。

exCRT

本质是同余方程组的合并。就是 CRT 解决的问题去掉了一个互质。

比如说现在我们有两个方程组，\(\begin{cases}x\equiv r_1 \pmod {m_1} \\ x\equiv r_2\pmod {m_2}\end{cases}\)，令 \(\begin{cases}x = k_1m_1 + r_1 \\ x = k_2m_2 + r_2\end{cases}\)，则有 \(k_1m_1 + r_1 = k_2m_2 + r_2\)。移项得 \(k_1m_1 + k_2(-m_2) = r_2 - r_1\)。运用飞天意面神教的咒语exgcd 的知识我们知道当 \(\gcd(m_1, m_2) \not | (r_2 - r_1)\) 时方程无解，否则可以用 exgcd 的知识求出来一组解 \(k_1',k_2'\) 满足 \(k_1'm_1 + k_2'm_2 = \gcd(m_1, m_2)\)。一个合法的解就是 \((\dfrac{k_1'(r_2 - r_1)}{\gcd(m_1, m_2)} + o\dfrac{m_2}{\gcd(m_1, m_2)})m_1+(\dfrac{-k_2'(r_2 - r_1)}{\gcd(m_1, m_2)} - o\dfrac{m_1}{\gcd(m_1, m_2)})m_2 = r_2 - r_1\)。\(o\) 是整数。

即 \(k_1 = (\dfrac{k_1'(r_2 - r_1)}{\gcd(m_1, m_2)} + o\dfrac{m_2}{\gcd(m_1, m_2)})\)，代入进 \(x\) 得 \(x = (\dfrac{k_1'(r_2 - r_1)}{\gcd(m_1, m_2)} + o\dfrac{m_2}{\gcd(m_1, m_2)})m_1 + r_1\)，也就是 \(x = \dfrac{k_1'm_1(r2-r1)}{\gcd(m_1, m_2)} + o\dfrac{m_1m_2}{\gcd(m_1, m_2)} + r_1\)。

我们觉得 \(o\dfrac{m_1m_2}{\gcd(m_1, m_2)}\) 很丑，因此我们用飞天意面神教的咒语同余的方法两边同时对 \(\dfrac{m_1m_2}{\gcd(m_1, m_2)}\)取余消掉这项避免掉 \(o\) 的求解，同时这样做也能让我们完成合并两个同余式的使命，就能得到 \(x\equiv \dfrac{k_1'm_1(r_2- r_1)}{\gcd(m_1, m_2)} + r_1\pmod {\dfrac{m_1m_2}{\gcd(m_1, m_2)}}\)。

代码里面有个小细节，\(r_2 - r_1\) 是负数怎么办？

我们可以 \([(r_2 - r_1) \bmod m_2 + m_2]\bmod m_2\) 一下。

由于我也没有好的方法说明，如果大家有好的方法欢迎用邮箱发给小 SX 哒（我的 QQ 邮箱是 2392303708@qq.com）。就是令 \(M\) 为 \(\operatorname{lcm}(m_1, m_2, \dots, m_k - 1)\)，我们已经知道了前 \(k - 1\) 个方程的通解 \(x\)，现在我们要求一个 \(x'\) 满足 \(x'\equiv r_k \pmod {m_k}\)，\(x'\) 可以表示成 \(x + tM\) 的形式，也就是 \(tM + x\equiv r_k\pmod{m_k}\)，移项得 \(tM\equiv r_k - x\pmod{m_k}\)。容易看出来 \(x\) 其实对应着我们上面的 \(r_1\)，\(r_k\) 对应着我们上面的 \(r_2\)。

这是一个简单的线性同余方程，我们可以用扩欧解掉。

这种方式更加简单，可拓展性强，你可以用类似的方法秒杀 https://www.luogu.com.cn/problem/P4774

但缺点在于貌似比较迷。。。？毕竟没有上面的推导雀食布吉岛为什么模数就直接取它们的 \(\operatorname{lcm}\) 对八┓( ´∀` )┏

屠龙勇士这题貌似没啥可讲的，毕竟推出来式子感觉比较显然。。。？

无脑套个平衡树就挺无聊的就，，，但是自己到现在还不能默写平衡树，，，wtf，，，

明天去背 fhq 板子 qwq！一定要背下来惹。。。

虽然正常考试一般不考这玩意但是背下来貌似能省很多动脑的内容。。。套板子万岁！┓( ´∀` )┏

巴特西

CRT 与 exCRT

CRT

exCRT

最新文章

热门文章