线性同余方程组
基本问题是求解形如下面的 线性同余方程组
\[\begin {aligned} \begin {cases} x \equiv a_1 \pmod {p_1} \\ x \equiv a_2 \pmod {p_2} \\ ... \\ x \equiv a_n \pmod {p_n} \end {cases} \end {aligned} \]在 \(\operatorname {OI}\) 中有 广泛的应用
建议阅读 基本概念，同余关系 章节，了解基本概念与先要知识
全文 绝大多数 内容是对 [0] 中讲述的 粗略抄写 和 胡乱加工
1. 中国剩余定理
即 \(CRT\)，全称 \(Chinese ~ Remainder ~ Theorem\)，用于求解 模数两两互质 的 线性同余方程组
即需要保证对于任意 \(i, j \in [1, n]\)，\(p_i \perp p_j\)（无需保证 \(p \in \mathbb P\)）
这十分的 小学奥数，当时就有一类知名的问题
韩信点兵
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
—— 《孙子算经》
\(x \equiv 2 \pmod 3, x \equiv 3 \pmod 5, x \equiv 2 \pmod 7, x_{\min} ?\)
这东西 很典，但是当时的做法可能 千奇百怪，并不具有 普适性
可能换一个 模数 / 余数 / 条件数量 就寄了
而 中国剩余定理 就很牛！它可以 程式化的 解决一切 模数两两互质 情况下的此类问题
形式化的流程
此处 要解决的问题 是 最开始给出的 一般线性同余方程组，保证 模数两两互质
-
找到 \(N = \prod \limits _ {i = 1} ^ {n} p_i\)，同时令 \(N_i = \dfrac N {n_i}\)
-
于是我们就可以把 多个式子 变成如下 一个式子，也就是得到了 通解
\[x \equiv \sum \limits _ {i = 1} ^ {n} { a_i N_i N_i ^ {-1} } \pmod N \]
乍一看感觉这东西 很怪，于是我们来仔细解释一下 这个式子的含义
显然，\(N\) 是 所有模数的 \(\operatorname {lcm}\)（保证 模数两两互质）
故 \(N _ i\) 即是 除了 \(p_i\) 以外模数的 \(\operatorname {lcm}\)，显然，包含 \(N_i\) 这个因式的数被除 \(p_i\) 外 所有模数整除
换言之，\(a_i N_i N_i ^ {-1}\) 这一项 不会 对其他任何模数产生 余数上的影响
也就是说，和式 中 某一项 只对原方程组中某一个方程有贡献，任意两项间 贡献独立
这就解释了为什么我们可以用 加法 连接不同项，而不是 乘法 之类的运算
考虑分析 第 \(i\) 项对第 \(i\) 个方程的贡献，由于 \(N _ i N _ i ^ {-1} \equiv 1 \pmod {p_i}\)
故显然，我们乘上 \(a_i\) 即可使得其 模 \(p_i\) 的余数变为 \(a_i\)，满足方程
例子
为了理解这个流程，我们回到刚刚 韩信点兵 的例子上
考虑找到 \(N = 3 \times 5 \times 7 = 105\)，\(N_i = {35, 21, 15}\)，\(N_i ^ {-1} = {2, 1, 1}\)
容易发现有 \(N_1 = \operatorname {lcm} (p_2, p_3) = \operatorname {lcm} (5, 7)\)，\(N_2, N_3\) 同理
显然 \(N_i N_i ^ {-1} = {70, 21, 15}\)，其分别满足 \(\bmod 3, \bmod 5, \bmod 7 = 1\)
同时，满足 \((\bmod 5, \bmod 7)\)，\((\bmod 3, \bmod 7)\)，\((\bmod 5, \bmod 7)\) 为 \(0\)，不会做额外贡献
于是我们将之 分别乘上 \(a_i\)，得到 \(a_i N_i N_i ^ {-1} = 140, 63, 30\)，显然分别满足第 \(i\) 个式子条件
加和，得出最终结果 \(x \equiv 233 \pmod {N = 105}\)，于是最小解 \(x = 23\)，满足条件
上述流程不难理解，于是最后只剩代码实现了
inline long long EXGCD (const long long a, const long long b, long long &x, long long &y);
inline long long CRT (const long long * P, const long long * R, const int N) {
long long M = 1, T = 0, A = 0, x, y;
for (int i = 1; i <= N; ++ i) M = M * P[i];
for (int i = 1; i <= N; ++ i) {
T = M / P[i], EXGCD (T, P[i], x, y);
A += ((__int128) 1 * (R[i] * T) * (x < 0 ? x + P[i] : x)) % M;
}
return A % M;
}
板子题 Luogu P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 检验正确性
有一组新的 \(Hack\)，很强，但很没意思
提示
考虑 R[i] * T 可能爆 int 但是小于 M（流程中的 N，故 中途取模 没用） 然后再乘上 x（N_i 的逆元）就可能 爆掉 long long，必须要 __int128 才行
2. 扩展中国剩余定理
即 \(exCRT\)，用于求解 模数并不两两互质 的 更加广泛的情况
其实很多 \(ex\) 都是扩展 模数不是质数 / 不互质 / ... 这样的情况
先考虑只有 两个式子 的简单情况，如果我们也能 将其合并成一个，那么 推广就容易了
\[\begin {aligned} \begin {cases} x \equiv a_1 \pmod {p_1} \\ x \equiv a_2 \pmod {p_2} \end {cases} \end {aligned} \]即有 \(x = a_1 + k_1p_1 = a_2 + k_2p_2\)，容易发现，求解 \(x\)，无异于求解 \(k_1, k_2\)，简单变形可得
\[k_1 p_1 - k_2 p_2 = a_2 - a_1 \]\(\operatorname {exgcd}\) 求解即可，当 \(\gcd (p1, p2) \nmid a_2 - a_1\) 时，该方程无解，即 原方程组无解
当 模数不互质 时，原方程组 确实会有 无解的情况，例如 \(x \bmod 4 = 2, x \bmod 6 = 1\) 时
于是我们得到 \(x = a_1 + k_1 p_1 = a_2 + k_2 p_2\) 这样的 特解（其中 \(k_1, k_2\) 已被解出）
我们就可以 将之转化成一个新的方程
\[x \equiv a_1 + k_1 p_1 \pmod {\operatorname {lcm} (p_1, p_2)} \]\(a_1 + k_1 p_1\) 是 一组特解，\(\operatorname {lcm} (p_1, p_2)\) 保证转化前的 两个方程 始终成立
于是 依次合并，就可以推广到 \(n\) 个方程的方程组，解决原问题
inline long long Mul (long long a, long long b, const long long MOD) {
long long Ret = 0;
while (b) {
if (b & 1) Ret = (Ret + a) % MOD;
a = (a + a) % MOD, b >>= 1;
}
return Ret;
}
inline long long EXCRT (const long long * P, const long long * R, const int N) {
long long M = 1, T = 0, K = 0, S = 0, x, y, AP = P[1], AR = R[1];
for (int i = 2; i <= N; ++ i) {
T = EXGCD (AP, P[i], x, y), S = ((R[i] - AR) % P[i] + P[i]) % P[i];
if (S % T) return -1;
M = S / T, K = P[i] / T, x = Mul (x, M, K), y = Mul (y, M, K);
AR = (AR + x * AP), AP = AP * K, AR = (AR % AP + AP) % AP;
}
return (AR % AP + AP) % AP;
}
需要一个 快速乘 来避免溢出，也可以使用
__int128（好像更慢）为什么解只需要 模 \(K = \dfrac {p_2} {\gcd (p_1, p_2)}\) 而不是 \(\operatorname {lcm} (p_1, p_2)\)？
因为下面需要乘一个 \(p_1\)（\(a_1 + k_1p_1\)），故这里没必要对 \(\operatorname{lcm}\) 取模
板子 Luogu P4777 【模板】扩展中国剩余定理（EXCRT），上述实现 可能并不精细