历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

【数论笔记】同余、欧几里得及其扩展 + 逆元、中国剩余定理及其扩展

作者：

CCCkk , 2022-02-13 11:44:48 , 所有人可见 , 阅读 510

3

2

笔记汇总

欧几里得算法（辗转相除法）

此算法的关键在于证明:

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

设 $gcd(a, b) = d$，则 $a \perp d$ $\&\&$ $b \perp d$

又因为 $a = c * b + a \% b$，其中 $c = ⌊a / b⌋$

由 $a \perp d$ 和 $(c * b) \perp d$ 可知，$a - (c * b) = a \% b \perp d$，得证。

当 $a \% b = 0$ 时

因为 $a \% b = 0$，意味着 $a \perp b$，直接返回 $b$ 即可

当 $a \% b != 0$ 时

因为 $a \% b != 0$，意味着 $a$ 不能整除 $b$，通过辗转相除法 等价变形 解决

时间复杂度为 $O(logn)$

int gcd(int a, int b)
{
    if (!b) return a;
    return (b, a % b);
}

若扩展为多个数，则时间复杂度为 $O(nlogn)$

扩展欧几里得算法

对于一组整数 $a, b$，求出另一组整数 $x, y$，使其满足 $ax + by = gcd(a, b)$

当 $a \% b = 0$ 时

因为 $a \% b = 0$，意味着 $a \perp b$，两者最大公约数为 $b$

所以 $by’ + (a \% b)x’$ 的下层 $ax + by = a$

故，$x = y’ = 1, y = x’ = 0$

当 $a \% b != 0$ 时

已知 $gcd(a, b) = gcd(b, a \% b) = d$，并找到两个整数 $x’, y’$，

满足 $by’ + (a \% b)x’ = gcd(b, a \% b) = d$，

根据 $a \% b = a - ⌊\frac{a}{b}⌋ * b$，

进而推出 $by’ + (a - ⌊\frac{a}{b}⌋ * b)x’ = d$

提取公因式后可得 $ax’ + b(y’ - ⌊\frac{a}{b}⌋ * x’) = gcd(b, a \% b) = gcd(a, b) = d$

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

所以提取公因式后可得 $x = x’$，$y = y’ - ⌊\frac{a}{b}⌋ * x’$

因此可以采取递归算法先求出下一层的 $x’$ 和 $y’$ 再利用上述公式回代即可

规律 1

任意两组扩展欧几里得的解之间总有一个整数 $k$，满足

$x = x_0 + k(\frac{b}{d})$

$y = y_0 - k(\frac{a}{d})$

代码

int exgcd(int a, int b, int &x, int &y) // 千万不能将 & 给忘了，在后面会用到这里算出的 x 和 y 的值
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);  // 从后往前更新，先求出下层的 x'、y' 
    y -= a / b * x;                 // 再用公式回代

    return d;
}

同余 $ax ≡ b(mod m)$

性质 1

因为 $ax \% m = b \% m$

所以 $(m, ax \% m) = (m, b \% m)$

逆推 $(ax, m) = (b, m)$

性质 2

因为 $(ax - b) \% m = 0$

所以 $ax - b = m * (-y) (y ∈ Z)$

等价于求 $ax + my = b$

可以用扩展欧几里得算法解决。

$Bezout$ 定理及其证明

对于不定方程 $ax + by = c$，当且仅当 $c \perp (a, b)$ 时有整数解。

一定存在 $x,y$ 为整数，使得 $ax + by = (a, b)$ 成立。

证明

设 $d = (a, b)$，则有 $d \perp a,d \perp b$，则对于任意整数 $x, y$ 都有 $d \perp ax + by$

若 $ax + by$ 不整除 $d$，也就意味着 $x, y$ 中有至少一个不是整数。

那有分数 $x, y$ 满足 $ax + by \perp d$ 吗？

有，但要构造这种情况，也是先假定有整数 $x’,y’$ 满足 $ax’ + by’ = ax + by$，也就是已存在整数解，第一条证毕

设 $s$ 为 $ax + by$ 的最小正值，记 $s = ax_0 + by_0$，有 $d \perp s$

因为 $ax_0, by_0$ 都为整数，且与 $(a, b)$ 为倍数关系，又因为 $ax_0, by_0$ 分别与 $(a, b)$ 为倍数关系。

故 $s = (a, b)$，因为对于任何正整数都有 最大公因数，第二条证毕

同余的归元操作

因为扩展欧几里得所求的只是一个 基准解，但这个可行解很有可能 不符合 题目要求。

而现在，我们就要将 基准解 变为 可行解。

例如 $ax + by = d$，但我们要求的是 $= c$ 时，$x’,y’$ 的值，那么，可以根据等式的性质

将 $(ax + by) * \frac{c}{d} = d * \frac{c}{d}$

故最后可得 $x’ = x * \frac{c}{d}, y’ = y * \frac{c}{d}$

但需要注意的是，此时 $x’、y’$ 并不一定是正整数，所以我们需要将 可行解 转化为 合理解

由所有解的通式可得：

$x = x_0 + k(\frac{b}{d})$

$y = y_0 - k(\frac{a}{d})$

我们就可以靠这个公式，来将所需要的解进行转换。

逆元

前言

在数论中，如果 $ab ≡ 1 (mod p)$ 时，则 $a$ 和 $b$ 在膜 $p$ 意义下互为乘法逆元，记作 $a = inv(b)$。

在实际练习中，加减法和乘法 对取模运算是 封闭的，可以通过取模来避免溢出。

但若答案落到了负数域，可以通过 $(ans \% mod + mod) \% mod$ 来转达正数域。

而且，已经在负数域的情况下，所有减去的数取模后都会被压缩到限制以内，

如果原答案本身就在正数域，等于说原答案由至少一个 $mod$ 大小的边限值组成，

因为大于边限值的数都要取模，则增加的这个边限值起到了垫付的作用，补齐了失去的正数域。

逆元的意义

但是，除法并不符合 封闭性，这就需要引入逆元这个概念了。

举一个例子：

$(12 / 3) \% 10 = 4$

如果我们计算 $3$ 在膜 $10$ 意义下的逆元

$inv(3) = x$

$3x ≡ 1 (mod(10)) => 3x + 10y = 1$

解，得： $inv(3) = x = 7$

代回原例看看：

$12 \% 10 * inv(3) \% 10 = (2 * 7) \% 10 = 4$

由于 $(a, m)$ 需要整除 $1$，可见逆元仅在数与模数互质的情况下存在。

逆元 $x$ 使得 $a/b ≡ ax (mod m)$

LL exgcd(LL a, LL b, LL &x, LL &y)// 扩欧
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
LL inv(LL a, LL p)
{
    LL x, y;
    if (exgcd(a, p, x, y) != 1) // 无解的情形
        return -1;
    return (x % p + p) % p;     // 合理解,由通项公式可知
}

中国剩余定理

中国剩余定理，也叫 孙子定理，之所以叫这个名字，是因为《孙子算经》中有这样一个问题：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物最少几何？

这个问题的本质，就是一个 同余方程组

$\begin{cases}x\equiv b_1 \pmod{a_1}\\x\equiv b_2 \pmod{a_2}\\...\\x\equiv b_n \pmod{a_n}\end{cases}$

后来的数学家在研究中发现，这一方程组有解的一个充分条件是 $a_1, a_2,…a_n$ 两两互质。

我们先从《孙子算经》里的具体问题出发，题意的表达如下：

$\begin{cases}x\equiv 2\pmod{3}\\x\equiv 3\pmod{5}\\x\equiv 2\pmod{7}\end{cases}$

要想直接找到一个 $x$，使方程组成立，几乎是不可能的，但若我们将它拆成熟悉的 单个方程，

解决起来则 容易许多，这启发我们用 多个未知数 去替代 $x$

$\begin{cases}n_1\equiv 2\pmod{3}\\n_2\equiv 3\pmod{5}\\n_3\equiv 2\pmod{7}\end{cases}$

但是，未知数的值 并不相同，不属于一个通解，我们要找的是 未知数值 相同的可行解。

注意：绝对不可以将 $x = n_1 + n_2 + n_3$，这不是一个正确的 归元操作。

如果要令这个等式成立，则必须满足 $n_1 + n_2 + n_3 ≡ 2 (mod 3)$，

这也意味着要满足 $n_2 + n_3$ 也是 $3$ 的倍数，简化后，可表示为 $n_2, n_3$ 满足是 $3$ 的倍数。

如此，$x = n_1 + n_2 + n_3$ 成立的条件是 $n_1、n_2、n_3$ 分别是 $35、21、15$ 的倍数。

我们将 $n_1、n_2、n_3$ 分别表示 $35m_1、21m_2、15m_3$，构成的方程组如下，

$\begin{cases}35m_1\equiv 2\pmod{3}\\21m_2\equiv 3\pmod{5}\\15m_3\equiv 2\pmod{7}\end{cases}$

在中国剩余定理中，模数两两互质，则 模数的乘积 亦两两互质，

所以，我们用 扩展欧几里得算法，解决这道问题的 基准解，等价于求 这些数在不同模数下的逆元。

$\begin{cases}35w_1\equiv 1\pmod{3}\\21w_2\equiv 1\pmod{5}\\15w_3\equiv 1\pmod{7}\end{cases}$

解得 $w_1 = 2, w_2 = 1, w_3 = 1$，然后将其转化为 可行解，

$\begin{cases}m_1=2w_1=4\\ m_2=3w_2=3\\ m_3=2w_3=2\end{cases}$

并将得到的解通分，真正转化为 可行解。

$\begin{cases}n_1=35m_1=140\\ n_2=21m_2=63\\ n_3=15m_3=30\end{cases}$

解：得 $x = 140 + 63 + 30 = 233$，但还没完，我们还需要将它转化为 合理解，但在此也可表示为 最优解。

$x = 233 % 105 = 23$，为什么模数是 $105$ 呢？

因为 $105$ 是 $3、5、7$ 的最小公倍数，不会在取模时产生余数，即 不会影响同余性质。

现在我们把刚刚这个过程一般化。我们设 $p=\prod_{i=1}^{n}a_i$ （即所有模数的乘积），并设 $r_i=\frac{p}{a_i}$ （在 “物不知数” 中即为 $35、21$ 和 $15$）。于是 $w_i=\left.\text{inv}\left(r_i\right)\right|_{a_i}$ （表示 $r_i$ 在模 $a_i$ 意义下的逆元）， $m_i = b_iw_i$ ，而 $n_i = r_im_i$ ，所有 $n_i$ 相加即得 $x$ 。

我们把以上这些综合成一个（看起来可能有点劝退的）公式即是：

$x \equiv \sum_{i=1}^{n}b_i{r_i\left.\left[r_i\right]^{-1}\right|_{a_i}}\pmod{p}$

现在我们来看（可能相对没那么劝退的）代码吧：

inline LL CRT(LL a[], LL b[], LL n)  // a是模数数组，b是余数数组，n是数组长度
{
    LL p = 1, x = 0;
    for (int i = 0; i < n; ++i)
        p *= a[i];
    for (int i = 0; i < n; ++i)
    {
        LL r = p / a[i];
        x += (b[i] * r * inv(r, a[i])) % p;   // 逆元的求法参见上文
    }
    return x % p;
}

扩展中国剩余定理

上文所述内容都有一个前置条件，即 模数两两互质，

若模数不满足此条件，就要用 扩展中国剩余定理 解决。

0 评论

App 内打开