扩展中国剩余定理(Excrt)笔记

发布时间 2023-12-23 08:57:12作者: Lcy++

扩展中国剩余定理(excrt)

本来应该先学中国剩余定理的。但是有了扩展中国剩余定理,朴素的 CRT 就没用了。

扩展中国剩余定理用来求解如下形式的同余方程组:

\[\begin{cases} x \equiv a_1\ ({\rm mod}\ b_1) \\ x\equiv a_2\ ({\rm mod}\ b_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ b_n)\end{cases} \]

扩展中国剩余定理的基本思想是合并,通过 \(n - 1\) 次合并,将一个大的同余方程组合并成一个同余方程。

假设现在有两个同余方程:

\[\begin{cases} x \equiv a\ ({\rm mod}\ A) \\ x\equiv b\ ({\rm mod}\ B) \end{cases} \]

现在要将他们合并。首先转化成不定方程:

\[\Rightarrow \begin{cases} A | (x - a) \\ B | (x - b) \end{cases} \]

\[\Rightarrow \begin{cases} x - a = Ak_1 \\ x - b = Bk_2 \end{cases} \]

\[\Rightarrow \begin{cases} x = a + Ak_1 \\ x = b + Bk_2 \end{cases} \]

\[\Rightarrow a + Ak_1 = b + Bk_2 \]

\[\Rightarrow Ak_1 - Bk_2 = b - a \]

成功转化成了系数为 \((A, -B, b - a)\) 的不定方程,使用 exgcd 求出他的一个根。因此转化成了一个同余方程:\(x \equiv Ak_1 + a (\bmod \ \text{lcm}(A, B))\)。合并完成。

// 合并 x = a(mod A), x = b(mod B) 两个方程
// 返回的是新的 a', b',满足 x = a'(mod b')
PII merge(int a, int A, int b, int B) {
	int k1, k2; int d = exgcd(k1, k2, A, B);
	k1 = k1 * (b - a) / d;
	int p = A / d * B; return {(A * k1 + a) % p, p};
}

bonus:

  1. 如果 \(x\) 的系数不为 \(1\)

也就是 P4774 [NOI2018] 屠龙勇士

求解形如:

\[\begin{cases} p_1 x \equiv a_1\ ({\rm mod}\ b_1) \\ p_2 x\equiv a_2\ ({\rm mod}\ b_2) \\ ... \\ p_n x \equiv a_n\ ({\rm mod}\ b_n)\end{cases} \]

Excrt 因为 \(x\) 的系数是一,因此可以直接联立两个不定方程。也尝试将这个东西转化成不定方程的形式。假设现在需要合并的两个同余方程是:

\[\begin{cases} px \equiv a (\bmod \ b) \\ Px \equiv A(\bmod \ B)\end{cases} \]

\[\Rightarrow \begin{cases} b | (px - a) \\ B | (Px - A) \end{cases} \]

\[\Rightarrow \begin{cases} px - a = k_1 b \\ Px - A = k_2 B \end{cases} \]

\[\Rightarrow \begin{cases} px - k_1 b = a \\ Px - k_2 B =A\end{cases} \]

然后发现两个 \(x\) 的系数不同,不能直接合并了。而这两个柿子两边又不能同时除以 \(p\) 或者 \(P\),因为不保证逆元存在。这就非常难搞。

一个神奇的思路是直接解出两个方程。以第一个方程为例,方程中只有两个未知数 \(x\)\(-k_1\),可以解出一个特解 \(x_0\)。那么所有 \(x\) 就可以表示成:

\[x = x_0 + \dfrac{b}{(p, b)} \times \alpha \]

同理解第二个方程,可以得到

\[x = x_1 + \dfrac{B}{(P, B)} \times \beta \]

我们惊奇的发现这两个 \(x\) 的系数相同了。所以可以合并一下:

\[x_0 + \dfrac{b}{(p, b)} \times \alpha = x_1 + \dfrac{B}{(P, B)} \times \beta \]

里面只有 \(\alpha, \beta\) 两个未知数,解出他们两个就可以得到 \(x\)

  1. 扩展中国定理进行模数非质数的合并

古代猪文

\(\dbinom{n}{m} \bmod \ 999911658\) 的值。

\(999911658\) 质因数分解得到:\(999911658 = 2 \times 3 \times 4679 \times 35617\)

因此可以对 \(2, 3, 4679, 35617\) 分别做一遍 \(\text{Lucas}\),得到下面的同余方程:

\[\begin{cases} x \equiv a_1(\bmod \ 2) \\ x \equiv a_2(\bmod \ 3) \\ x \equiv a_3(\bmod \ 4679) \\ x \equiv a_4(\bmod \ 35617) \\ \end{cases}\]

可以直接用 excrt 合并一下。

另外一个应用是扩展卢卡斯。其基本思路也是将模数拆成若干质因数的次方,计算后 excrt 合并。