前のページ

数论进阶

提高组的简单数论

记录一些结论作为备忘可以时常翻翻。

模意义下的数和运算

模相关简单运算

对于整数 $a, b$,满足 $b \gt 0$,那么存在唯一的整数 $q, r$,满足 $a = bq + r$,其中 $0 \leq r \lt b$。在这之中,我们称 $q$ 为商、$r$ 为余数。

余数使用 $a \bmod b$ 或者 $a % b$ 表示

一下是一些常见的有关模的运算:

  • $(a + b) \bmod M = (a \bmod M + b \bmod M) \bmod M$
  • $(a - b) \bmod M = (a \bmod M - b \bmod M) \bmod M$
  • $(a \times b) \bmod M = (a \bmod M \times b \bmod M) \bmod M$

注意到除法并不适用,下文会引出乘法逆元解决模意义下的除法运算。

同余

如果两数 $x, y$ 除以 $b$ 的余数相等,那么称 $x, y$ 模 $b$ 同余,记作 $x \equiv y (\bmod b)$。

以下性质显然:

  • 反身性:$x \equiv x (\bmod M)$
  • 对称性:$x \equiv y (\bmod M)$,则 $y \equiv x (\bmod M)$
  • 传递性:$x \equiv y (\bmod M), y \equiv z (\bmod M)$,则 $x \equiv z (\bmod M)$

根据我们刚刚提到的模意义下的运算规律,还可以得到以下性质:

  • 同加性:若 $x \equiv y (\bmod M)$,则 $x + z \equiv y + z (\bmod M)$
  • 同乘性:若 $x \equiv y (\bmod M)$,则 $x \times z \equiv y \times z (\bmod M)$
  • 同幂性:若 $x \equiv y (\bmod M)$,则 $x^n \equiv y^n (\bmod M)$

下面这条性质非常重要:

$$x \equiv y (\bmod b) \Leftrightarrow b | (x - y)$$

同余方程和裴蜀定理

裴蜀定理

在 OI 中,形如 $ax + by = c$ 的二元一次不定方程只需要解决 $a, b, c$ 都是整数的情况。

对于整数 $a, b$,设他们的最大公约数 $\gcd(a, b) = d$,一定存在一组整数 $(x, y)$ 使得 $ax + by = d$。

对于整数 $a, b, c$,$ax + by = c$ 有整数解当且仅当 $\gcd(a, b) \lvert c$。

扩展欧几里得算法

欧几里得算法求 $a, b$ 最大值的过程:

  1. 当 $b = 0$ 时,$a, b$ 的最大公约数就是 $a$
  2. 求出 $b, a \bmod b$ 的最大公约数,设为 $g_0$
  3. 令 $g = g_0$,$g$ 就是 $a, b$ 的最大公约数

仿照欧几里得算法求解不定方程的过程:

  1. 当 $b = 0$ 时,$ax + by = d$ 的解是 $x = \dfrac{d}{a}$,$\forall y$。
  2. 求出 $bx + (a \bmod b)y = d$ 的一组解,设为 $(x_0, y_0)$。
  3. 令 $(x, y) = f((x_0, y_0))$,$(x, y)$ 就是 $a_x + b_y = d$ 的一组解。其中 $f((a, b))$ 指将 $(a, b)$ 这一对数进行变换。

变化如下:令 $(x, y) = (y_0, x_0 - \lfloor \dfrac{a}{b} \rfloor y_0)$。

可以发现,设 $a_x + b_y = d = k \times \gcd(a, b)$,那么每次迭代的得到的解都是在求解 $ax + by = \gcd(a, b)$ 时得到的解的 $k$ 倍,所以不管 $d$ 取多少,最后的迭代中取 $x = k, y = 0$ 是没有问题的。

C++ Template:

<template typename T>

T exgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    T d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

乘法逆元

若 $ax \equiv 1 (\bmod p)$,则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元,记为 $a^{-1} (\bmod p)$

注意,在 $[0, p)$ 这一范围内,模 $p$ 的逆元(若存在)是唯一的。

求解乘法逆元的方法有两种:

扩欧求解乘法逆元

容易发现乘法逆元的定义式和 $\exists y, ax + py = 1$ 等价。这也就是一个关于 $a, p$ 的不定方程,使用扩欧解决,又裴蜀定理易得,存在 $a$ 在模 $p$ 意义下的逆元当且仅当 $\gcd(a, p) = 1, a \bot b$。

C++ Template:

<template typename T>

T exgcd(T a, T b, T &x, T &y) {
    // 参见上文
    ...
}

T inv(int a, int p) {
    int x, y;
    exgcd(a, p, x, y);
    return x;
}

费马小定理求解乘法逆元

费马小定理定义如下:

若 $\forall p \in \mathbb{P}$,且 $a$ 不是 $p$ 的倍数,则 $a^{p - 1} \equiv 1 (\bmod p)$。

假设 $p$ 是质数,可知如果 $a$ 不是 $p$ 的倍数,有 $a \times a^{p - 2} = a^{p - 1} \equiv 1 (\bmod p)$。所以 $a$ 在模 $p$ 意义下的乘法逆元就是 $a^{p - 2}$,可以使用快速幂解决。

C++ Template:

<template typename T>

T expow(T a, T b, const T p) {
    T res = 1;

    for (; b; b >>= 1) {
        if (b & 1)
            res = 1ll * res * a % p;

        a = 1ll * a * a % p;
    }

    return res;
}

T inv(T a, T p) {
    return expow(a, p - 2, p);
}

同余方程与中国剩余定理

中国剩余定理

一般而言,中国剩余定理用来解决这样的一类同余方程组:

$$ \begin{cases} x \equiv a_1 (\bmod m_1) \\ x \equiv a_2 (\bmod m_2) \\ \vdots \\ x \equiv a_n (\bmod m_n) \end{cases} $$

其中,$m_1, m_2, \dots, m_n$ 两两互质,则对于任意整数 $a_1, a_2, \dots, a_n$,上面这个方程组有解。

解决方法如下:

  1. 设 $M = \prod^{n}_{i = 1} m_i$
  2. 设 $M_i = \dfrac{M}{m_i}$
  3. 设 $t_i = M^{-1}_i$ 为 $M_i \bmod m_i$ 的逆元(因为 $M_i$ 和 $m_i$ 互质,所以逆元一定存在)
  4. $x$ 的通解即为 $x = \sum_{i = 1}^n a_i t_i M_i + kM, k \in \mathbb{Z}$

扩展中国剩余定理

问题格式同上,但是没有了 $m_1, m_2, \dots, m_n$ 两两互质的条件。

引入定理:如果有特解 $x^*$,那么对于

$$ \begin{cases} x \equiv r_1 (\bmod m_1) \\ x \equiv r_2 (\bmod m_2) \end{cases} $$

的通解是 $x^* + k \times \text{lcm}(m_1, m_2)$,也就是 $x \equiv x^* (\bmod \text{lcm}(m_1, m_2))$

因此,处理 exCRT 的过程就是不断从方程组内取出两个方程,尝试进行合并然后再压入方程组内,如果无解退出,否则最后方程组内剩下的唯一一个方程就是解系。

线性筛和积性函数

暂待加工。

「馬鹿なわたしは歌うだけ」