欧几里得算法, 中国剩余定理

关于gcd(最大公约数)的欧几里得算法

朴素的欧几里得算法

欧几里得算法依赖于一个朴素的公式:

$$gcd(a, b) = gcd(b, a \% b)$$

如果 $ a, b $ 的最大公约数为 $c$ , 那么 $ a, a mod b $ 的最大公约数也为 $c$ .
易于理解的, $ gcd(a, b) \times lcm(a, b) = a \times b $ .
C++的代码实现:

int gcd(int a, int b) {
    return (b ? a : gcd(b, a % b));
}

exgcd(拓展欧几里得算法)

exgcd是干什么的

exgcd可以用于求解如下式子:

$$ax + by = gcd(a, b) \tag{1}$$

或者

$$ax \equiv gcd(a, b) \pmod{b}$$

然后进一步求解如下的情况:

$$ax + by = c$$

显然只要把第一个式子乘上 $ \frac{c}{gcd(a, b)} $ 就可以.

那我们如何求解呢
我们设 $d = gcd(a, b) $.
首先我们知道如下式显然成立:

$$a \% b = a - \lfloor \frac{a}{b} \rfloor \times b \tag{2}$$

考虑 $ gcd(a, b) $ 的求解过程:

$$gcd(a, b) = gcd(b, a \% b)$$

我们可以设想一个式子:

$$bx' + (a \% b)y' = d \tag{3}$$

把 $(1)$ 式代入 $(2)$ 式:

$$bx' + (a - \lfloor \frac{a}{b} \rfloor \times b)y' = d$$

化简得:

$$bx' + ay' - \lfloor \frac{a}{b} \rfloor \times b \times y' = d$$

再合并得:

$$b(x' + \lfloor \frac{a}{b} \rfloor y') + ay' = d \tag{4}$$

显然 $(4)$ 式和 $(1)$ 式是等价的.
于是我们便根据 $(4)$ 推出了 $(1)$ 的解.
显然一定有一组解在 $ ({a, b} )= ({1, 0}) $ 下 $ ax + by = gcd(a, b) $ 成立
于是我们便可以递归的写出代码:

std::pair <int, int> exgcd(int a, int b) {
    if(b == 0) {
        return {1, 0};
    }
    auto [x, y] = exgcd(b, b % a);
    return {y, x - a/b * y};
}

exgcd求逆元

定义一个同余方程 $ ax \equiv 1 \pmod{ b}$, 即 $ax + by = 1$ , 显然 $a, x$ 互为逆元.
运行 $exgcd(a, m) $ 即可.

附: 裴蜀定理 (Bézout’s Identity)

如果 $gcd(a, b) \nmid c $, 则原方程无整数解.

中国剩余定理(CRT)

朴素的中国剩余定理解决同余方程组

概念

例如对于以下的一元线性同余方程组：

$$\left \{ \begin{aligned} x &\equiv a_{1} \pmod{m_{1}} \\ x &\equiv a_{2} \pmod{m_{2}} \\ &\vdots \\ x &\equiv a_{n} \pmod{m_{n}} \\ \end{aligned} \right.$$

中国剩余定理给出了它的有解的判定条件, 并用构造法给出了在有解情况下解的具体形式.
中国剩余定理说明: 假设整数 $ m_1, m_2, … , m_n $ 其中任两数互质，则对任意的整数: $ a_1, a_2, … , a_n$ , 方程组有解，并且通解可以用如下方式构造得到:

1. 设 $ M = \prod_{i = 1}^{n} m_i, \ M_i = \frac{M}{m_i}$. 显然 $ M_i$ 是除 $m_i$ 之外 $m$ 集合中所有的元素的乘积.
2. 设 $t_i = M_{i}^{-1}$ , 即 $M_i$ 在 $\%m_i$ 意义下的倒数, 使得 $t_i \cdot M_i \equiv 1 \pmod{m_i} $.
3. 则 $x = kM + \sum_{i = 1}^{n}a_i t_i M_i$.

证明

易于理解的, $(a \cdot b) \% m = (a \% m) \cdot (b \% m), \ \ \ (a + b) \% m = (a \% m) + (b \% m)$.
对于给定的 $ i $, 有 $ \ \ t_i \cdot M_i \equiv 1 \pmod{m_i} $, 所以有 $ {a_i t_i M_t} \equiv a_i \pmod{m_i} $
而对于任意 $j \neq i $ , $ {a_i t_i M_t} \equiv 0 \pmod{m_i} $
显然 $\sum_{i = 1}^{n}a_i t_i M_i$ 是方程的一个解.
因为 $\forall i, M \% a_i = 0$, 所以 $k \cdot M + \sum_{i = 1}^{n}a_i t_i M_i$ 也是方程的解.

附上代码:

int _crt(int k) {
    int prod = 1, ans = 0;
    for(int i = 1; i <= k; i ++) prod *= m[i];
    for(int i = 1; i <= k; i ++) {
        int mi = prod / m[i];
        auto [x, y] = exgcd(mi, m[i]);
        ans += (a[i] * mi * x % prod);
        ans %= prod;
    }
    return (ans % prod + prod) % prod;
}

exCRT

裴蜀等式

对于任意两个整数 ( a ) 和 ( b )，以及它们的最大公约数 ( d )，裴祖等式一定可以写成：

$$d = \gcd(a, b) = ax + by$$

一个重要推论: $(a, b)$ 互质的条件是存在整数 $(x, y)$ 使得 $ax + by = 1$.

证明

考虑简单形式:

$$\left \{ \begin{aligned} x &\equiv a_{1} \pmod{m_{1}} \\ x &\equiv a_{2} \pmod{m_{2}} \\ \end{aligned} \right.$$

可转化为:

$$\left \{ \begin{aligned} x = ka_1 + m_1 \\ x = ka_2 + m_2 \\ \end{aligned} \right. \\ \ \ \ \ \ \ \ \ \ \ \ \Rightarrow x = k_1 m_1 + a_1 = k_2 m_2 + a_2 \\ \Rightarrow k_1 m_1 - k_2 m_2 = a_2 - a_1$$

根据 $Bézout’s Identity$ 若 $ gcd(m_1, m_2) \mid a_2 - a_1 $ 则原方程有解.
如果有解, 设 $ d = gcd(m_1,m_2) , p_1 = \frac{m_1}{d}, p_2 = \frac{m_2}{d}$

$$\Rightarrow k_1p_1 - k_2p_2 = \frac{ a_2 - a_1 }{d} \Rightarrow \frac{k_1d}{a_2 - a_1}p_1 - \frac{k_2d}{a_2-a_1}p_2 = 1;$$

显然 $gcd(p_1,p_2) = 1$ 可以用exgcd求解.
我们设该方程的一组解 $x, y$
$k_1 = \frac{x(a_2-a_1)}{d}, x = \frac{m_1x(a_2-a_1)}{d} + a_1$
原方程即转化为 :

$$x \equiv \frac{m_1 x (a_2 - a_1)}{d} \pmod {lcm(m_1, m_2)}$$

我们只要把方程转化 $n - 1$ 次就可以解决问题.
复杂度为 $\mathcal O((n - 1)\log n)$

Lucas定理

Lucas定理用于求解大组合数取模的问题, 其中模数必须为素数.

定义

$$\binom{n}{m} \bmod p = \binom{\lfloor n / p\rfloor}{\lfloor m / p\rfloor} \cdot \binom{n \bmod p}{m \bmod p} \bmod p$$

对于 $ \binom{\lfloor n / p\rfloor}{\lfloor m / p\rfloor} $ 可以递归求解.

( 证明 )

艹我不会