扩展中国剩余定理
讲解扩展之前，我们先叙述一下普通的中国剩余定理
中国剩余定理
中国剩余定理通过一种非常精巧的构造求出了一个可行解
但是毕竟是构造，所以相对较复杂
\[\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ x \equiv a_3 \pmod{m_3} \\ \dots \\ x \equiv a_n \pmod{m_n} \end{cases} \]
对于上述同余方程组，首先需要满足 \(m_1, m_2, m_3, \dots, m_n\) 互质
令 \(m = \prod_{i=1}^{n} m_i, M_i = m / m_i,\ t_i\) 是线性同余方程 \(M_it_i \equiv 1 \pmod {m_i}\) 的一个解
那么上述方程组有整数解，为 \(x = \sum_{i=1}^n a_iM_it_i\)
证明：
由于所有 \(m_i\) 互质，所以 \(M_i = m/m_i\) 是除了 \(m_i\) 之外的所有模数的倍数，所以 \(\forall j \ne i, a_iM_it_i \equiv 0 \pmod {m_k}\)
所以代入 \(x = \sum_{i=1}^n a_iM_it_i\) ，原方程组成立
中国剩余定理给出了方程的一个特解。通解可以表示为 \(x + km (k \in \Z)\) 。如果需要求最小的非负整数解，只需要让 \(x\) 对于 \(m\) 取模就是。
参考代码
【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷
#include <iostream>
typedef long long ll;
ll m[11], a[11], Mm[11], y[11];
// 扩展欧几里得算法，由于求出线性同余方程 Mi * ti = 1 (mod p) 的一个特解
// 上述同余式可以转化为 Mi * ti + k * p = 1
// 所以跑一个 extgcd(Mi, p, ti, k) 即可 （k没有用的）
void extgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return;
}
extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
int main() {
int n; scanf("%d", &n);
ll M(1);
// 这里读入，并求出m
for (int i = 0; i < n; i++) {
scanf("%lld%lld", m + i, a + i);
M *= m[i];
}
// 求出Mi
for (int i = 0; i < n; i++) {
Mm[i] = M / m[i];
}
// 求出每一个不定方程的特解
for (int i = 0; i < n; i++) {
ll x, tmp, mi = m[i];
extgcd(Mm[i], mi, x, tmp);
y[i] = (x + mi) % mi;
}
// 求和获得最小正整数解
ll x(0);
for (int i = 0; i < n; i++) {
x = (x + a[i] * Mm[i] * y[i]) % M;
}
printf("%lld\n", x);
return 0;
}
扩展中国剩余定理
还是考虑上述式子
\[\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ x \equiv a_3 \pmod{m_3} \\ \dots \\ x \equiv a_n \pmod{m_n} \end{cases} \]
此时，我们不保证 \(m_i\) 不一定两两互质，所以中国剩余定理不再适用
所以扩展中国剩余定理就开始发挥作用了
虽然说是扩展……但是两者思路很不一样
扩展中国剩余定理采用数学归纳法，或者说两两合并法
假如我们需要合并方程
\[x \equiv a_1 \pmod {m_1} \]
\[x \equiv a_2 \pmod {m_2} \]
我们将同余式改写
\[k_1m_1 + a_1 = x \]
\[k_2m_2 + a_2 = x \]
将两者相减，整理后可得
\[k_1m_1 - k_2m_2 = a_2 - a_1 \]
由于我们已知 \(m_1, m_2, a_1, a_2\) ，也就是说我们只需要知道 \(k_1, k_2\) 其中任意一个，就可以求出这时的 \(x\) 是个什么东西了
所以，联想到了……扩展欧几里得算法
可以参考文章： 算法学习笔记(1): 欧几里得算法及其扩展
我们令
\[\begin{aligned} d &= gcd(m_1, m_2) \\ c &= a_2 - a_1 \end{aligned} \]
那么化简一下有： \(k_1 m_1 - k_2 m_2 = c\)
所以我们求出 \(k_1' \frac {m_1}d + k_2' \frac {m_2}d = 1\)
那么换回去之后
\[\begin{aligned} k_1 &= k_1' \frac cd \\ k_2 &= -k_2' \frac cd \end{aligned} \]
由于 exgcd(a, b, x, y) 求出的是 xa + yb = gcd(a, b) 的一组解……所以需要 \(\frac cd\)
令 \(l = lcm(m_1, m_2) = m_1 m_2 / gcd(m_1, m_2)\)
那么此时 \(x \equiv k_1' m_1\frac cd + a_1 \pmod l\)
也就是可以得到 \(x\) 的一个解集 \(x \in X = \{kl + x|k \in \R\}\)
也就是说，我们将上述两个式子合并成了
\[x \equiv k_1' \frac cd m_1 + a_1 \pmod {lcm(m_1, m_2)} \]
那么考虑代码怎么写
typedef int data; // 方便换成long long
// 扩展欧几里得算法
inline data exgcd(data a, data b, data &x, data &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
data r = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return r;
}
// 最终的合并的结果会放在 a1, m1上
// 每一部分我会在后文详细的解释
inline bool merge(data& a1, data& m1, data a2, data m2) {
// section1: 为了防止溢出，需要适当的取模
data c = (a2 - a1) % m2;
if (c < 0) c += m2;
// section2: 通过拓展欧几里得算法求出上文中的 s = k1'
data d = gcd(m1, m2), s, t;
exgcd(m1 / d, m2 / d, s, t);
// +section2.5: 判断是否有解
if (c % d) return false;
// section3: 这里将s转化为上文中的 k
s = s / * c % m2;
if (s < 0) s += m2;
// section4: 正式合并
data lcm = m1 / d * m2;
a1 = (a1 + s * m1) % lcm;
if (a1 < 0) a1 += lcm;
m1 = lcm;
return true;
}
? ：为什么在前三个部分放在了模 \(m2\) 的情况下计算
为了避免溢出，我们需要将 \(s\) 转化为最小的正整数解
那么需要有代码 (s % (m2 / d) + m2 / d) % (m2 / d)
考虑到其实并不需要最小……所以为了方便，就直接是 (s % m2 + m2) % m2
考虑优化第二个模运算 （贼慢） ，所以换成了 if 语句，就是上面代码的写法
那么第一个部分为什么也可以取模呢？
考虑我们在第三部分放在了模 \(m_2\) 的意义下，所以我们可以把整个不定方程组放在模 \(m_2\) 的意义下，所以就可以把 \(c\) 对于 \(m_2\) 取模
? : 为什么在第二部分需要提前算出 \(gcd(m_1, m_2)\)
其实是不用的……只需要 data s, t; data d = exgcd(m1, m2, s, t); 也可以算出正确答案……
? : 判断有解是如何判断的
有无解实际上就是拓展欧几里得算法有无解
而判断拓欧算法有无解，也就通过贝祖定理验证
也就是说，对于不定方程 ax + by = c
如果 gcd(x, y) | c 则有解，否则无解
【模板】扩展中国剩余定理（EXCRT） - 洛谷
NOTICE ：在模板题上，由于可能会溢出……至于什么地方需要用龟速乘，请读者自行揣度
关于龟速乘： 算法学习笔记(2): 逆元及其应用 我提过一点
更详细的参考 快速乘总结 - 一只不咕鸟
查看更多关于算法学习笔记(9): 中国剩余定理(CRT)以及其扩展(EXCRT)的详细内容...