数论初识

Eray · 2022-07-31 10:00:27 · 个人记录

更好的阅读体验

本篇的用意在恶补认识 OI 中数论的基础部分。

一、约数、倍数与质合数

前置芝士

带余除法：a \div b = c \cdots\cdots r \Leftrightarrow a \bmod b = r
约数与倍数：a \bmod b = 0 \Leftrightarrow b 是 a 的约数 \Leftrightarrow a 是 b 的倍数
最大公因数：最大的数使得 c 同时为 a, b 的约数，记为 \gcd(a, b) 或 (a, b)
最小公倍数：最小的数使得 c 同时为 a, b 的倍数，记为 \operatorname{lcm}(a, b) 或 [a, b]
质数：p 是质数当且仅当 p 只有 1 和 p 两个约数（1 不是质数）
整除：a 是 b 的约数 \Leftrightarrow a\mid b
唯一分解定理：质因数分解方案唯一
质数无限
第 n 个质数是 O(n \log n) 级别的
\sum_{i=1}^n \frac{1}{i} = O(\log n)
a\mid c \land b\mid c \land (a, b) = 1\Rightarrow ab\mid c
a\mid bc \land (a, b) = 1 \Rightarrow a\mid c
ab = (a, b) \cdot [a, b]

附上一个黑科技：

这份代码可以计算 a \times b \bmod mod，但是 a \times b 可以爆 long long。

LL mul(LL a, LL b, LL mod) { return (a * b - (LL)((long double)a / mod * b + 0.5) * mod + mod) % mod; }

计算 gcd

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

\gcd(a, b) = \gcd(a - b, b) = gcd(a - 2b, b) = \cdots = \gcd(a \bmod b, b)

#### 其他算法 $$ \gcd(a, b) = \begin{cases} \gcd(\frac a2, \frac b2)&(2\mid a \land 2\mid b)\\ \gcd(\frac a2, b)&((2\mid a \land 2 \not\mid \ b) \lor (2 \not\mid \ a \land 2\mid b))\\ \gcd(a - b, b)&(2 \not\mid \ a \land 2 \not\mid \ b) \end{cases} $$ 复杂度 $O(\log a + \log b)$。 ### 裴蜀定理关于 x, y 的方程 $ax + by = d (a, b, x, y \in \mathbb Z)$ 有解 $\Leftrightarrow$ $(a, b)\mid d

证明

简单来说： 因为 a, b 都含有因子 (a, b)，且 x, y \in \mathbb Z，所以 d 也必须含有因子 (a, b)。
严谨证明：
令 g = (a, b)，则 g\mid a \land g\mid b，
令 a = a'g，b = b'g（a', b' \in \mathbb Z），则 d = ax + by = g(a'x + b'y) \Rightarrow \frac dg = a'x + b'y，
因为 a', x, b', y \in \mathbb Z，所以a'x + b'y \in \mathbb Z，所以 \frac dg \in \mathbb Z，所以 g\mid d，即 (a, b)\mid d。

拓展欧几里得（exgcd）

思路

解 ax + by = 1，其中 (a, b) = 1 \land a, b, x, y \in \mathbb Z
（可以将 ax + by = c 转换成 ax' + by' = 1 的形式）
原式可化为ax + by = (a, b) = 1
上式有解则表明 bx' + (a \bmod b)y' = (b, a \bmod b) = 1有解（裴蜀定理）
即 bx' + (a - b \lfloor \frac{a}{b} \rfloor)y' = (b, a \bmod b) = 1 有解
也即 b(x' - \lfloor \frac{b}{a} \rfloor y') + by' = (a, b \bmod a) = 1有解
那么 x = y'，y = x' - \lfloor \frac{a}{b}\rfloor y' 我们只需要递归下去就行了！
递归时求得 bx' + (a \bmod b)y' = 1 的解，然后用上述方法推 x, y
边界条件？
当 b = 0 时就得到 ax'' + 0y'' = 1 \Rightarrow ax'' = 1，可以证明此时 a = 1（因为 (a, b) = 1），即 x'' = 1, y'' = 0

代码

// 计算 ax + by = 1 的解，并返回 gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) { x = 1, y = 0; return a; }
    int g = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - a / b * y;
    return g;
}

例题

洛谷 P1082

// https://www.luogu.com.cn/problem/P1082

#include <cstdio>

const int N = 5e6 + 5;

typedef long long LL;

// ax + by = 1
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL g = exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return g;
}

int main() {
    LL a, b;
    std::scanf("%lld%lld", &a, &b);
    LL x, y;
    exgcd(a, b, x, y);
    while(x < 0) x += b;
    x %= b;
    std::printf("%lld\n", x);
    return 0;
}

应用

求逆元。（逆元见下方↓）

x \equiv a^{-1} \pmod b \Rightarrow ax \equiv 1 \pmod b \Rightarrow ax + by = 1 (y \in \mathbb Z)

可以用拓展欧几里得来推，解出的 x 即为 a 的逆元。

二、同余问题

前置芝士

a \equiv b \pmod m \Leftrightarrow m\mid (b - a)
a \equiv b \pmod m \land a \equiv b \pmod n \Rightarrow a \equiv b \pmod{[m, n]}
(k, m) = d \land ka \equiv kb \pmod m \Rightarrow a \equiv b \pmod{\frac md}

逆元

如果有 (b, m) = 1，那么 b 存在 \bmod m 意义下的逆元
令 a 在\bmod m 意义下的逆元为 b，则 ab \equiv 1 \pmod m a 的逆元记为 a^{-1}

\frac ab \bmod m = ab^{-1} \bmod m

欧拉定理

欧拉函数

所有的 n 满足 0 < n \le m，(n, m) = 1 构成了一个 \bmod m 的简化剩余系
n 的简化剩余系的个数记为 \phi(n) （希腊字母 \text{Phi} \Phi\phi，也写作φ）

\phi$ 是积性函数，即 $\phi(a) \phi(b) = \phi(ab)

欧拉定理

结论

(a, m) = 1 \Rightarrow a^{\phi(m)} \equiv 1 \pmod m

证明

令 S = \{x_1, x_2, \cdots, x_{\phi(m)}\} 为 m 的简化剩余系，
则 S' = \{ax_1, ax_2, \cdots, ax_{\phi(m)}\}也是 m 的简化剩余系
（因为 S' 两两不同且都与 m 互质）
所以 \prod_{x \in S'} x \equiv \prod_{x \in S} x \pmod m 即 a^{\phi(m)} \equiv 1 \pmod m

应用

a^{\phi(m)} \equiv 1 \pmod m \Rightarrow a^{-1} \equiv a^{\phi(m) - 1} \pmod m

如果 m 为质数，那么 a^{-1} \equiv a^{m - 2} \pmod m

线性求逆元

思路

令 \lfloor \frac{p}{i}\rfloor = k，p \bmod i = r（即 ki + r = p (r < i)），
则

\begin{aligned} p &\equiv 0 &\pmod p\\ ki + r &\equiv 0 &\pmod p\\ k\cdot i\cdot (i^{-1}\cdot r^{-1}) + r \cdot (i^{-1} \cdot r^{-1}) &\equiv 0 &\pmod p\\ kr^{-1} + i^{-1} &\equiv 0 &\pmod p\\ i^{-1} &\equiv -kr^{-1} &\pmod p\\ i^{-1} &\equiv -\lfloor \frac pi \rfloor \cdot (p \bmod i)^{-1} &\pmod p \end{aligned}

即 inv[i] = (-(p / i) * inv[p % i] + p) % p，
也即 inv[i] = (p - p / i) * inv[p % i] % p 。

代码

{% note no-icon info 代码 %}

// 筛出 n 以内的逆元
void get_inv() {
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

{% endnote %}

例题

洛谷 P3811

// https://www.luogu.com.cn/problem/P3811

#include <cstdio>

const int N = 20000528 + 5;

int inv[N];

int main() {
    int n, p;
    scanf("%d%d", &n, &p);
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    for(int i = 1; i <= n; i++) printf("%d\n", inv[i]);
    return 0;
}

中国剩余定理（CRT）

引入

先来看一个例子：

求最小的正整数 x，满足 x \equiv 2 \pmod 3，x \equiv 3 \pmod 5，x \equiv 2 \pmod 7。

解法：令

$b$ 为除以 $5$ 余 $1$ 的最小的 $3$ 和 $7$ 的公倍数，（$b = 21$） $c$ 为除以 $7$ 余 $1$ 的最小的 $3$ 和 $5$ 的公倍数。（$c = 15$）然后将 $a$ 乘上 2（$\bmod 3$ 的余数），b 乘上 3，c 乘上 2。（$a = 140$，$b = 63$，$c = 30$）则 $x = (a + b + c) \bmod 3 \times 5 \times 7 = 23

原理

要想让 [3, 5, 7]\mid a + b + c，最简单的方法是：

那么如何求这样的 a, b, c 呢？
以 a 为例，我们先求出除以 3 余 1 而且是 5 和 7 的公倍数的数，然后再乘 2。
即把 [5, 7] 乘上 [5, 7]^{-1} \pmod 3（此时除以 3 余数必为 1，而且是 5, 7 的倍数），再乘余数 2。
最后算出 a + b + c，然后模上 [3, 5, 7] 就是答案。

结论

若有方程：

\begin{aligned} x \equiv& r_1 \pmod {p_1}\\ x \equiv& r_2 \pmod {p_2}\\ &\vdots\\ x \equiv& r_n \pmod {p_n} \end{aligned}

其中 p_1, p_2, \cdots p_n 两两互质。
令 P = \prod_{i=1}^n p_i，P_i = \frac{P}{p_i}，v_i = (P_i)^{-1} \bmod {p_1}，
则方程的解为 x = \sum_{i=1}^n P_iv_ir_i \bmod P

代码

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
int crt() {
    int P = 1;
    for(int i = 1; i <= n; i++) P *= p[i];
    int x = 0;
    for(int i = 1; i <= n; i++) {
        int ret = 1;
        ret = ret * (P / p[i]) % P;
        int inv, tmp;
        exgcd(P / p[i], p[i], inv, tmp);
        while(inv <= 0) inv += p[i];
        inv %= p[i];
        ret = ret * inv % P;
        ret = ret * r[i] % P;
        x = (x + ret) % P;
    }
    return x;
}

例题

洛谷 P1495

// https://www.luogu.com.cn/problem/P1495

#include <cstdio>

const int N = 1e5 + 5;
typedef long long LL;

LL r[N], p[N];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) { x = 1, y = 0; return a; }
    LL g = exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return g;
}
LL crt() {
    LL P = 1;
    for(int i = 1; i <= n; i++) P *= p[i];
    LL x = 0;
    for(int i = 1; i <= n; i++) {
        LL ret = 1;
        ret = ret * (P / p[i]) % P;
        LL inv, tmp;
        exgcd(P / p[i], p[i], inv, tmp);
        while(inv <= 0) inv += p[i];
        inv %= p[i];
        ret = ret * inv % P;
        ret = ret * r[i] % P;
        x = (x + ret) % P;
    }
    return x;
}

int main() {
    std::scanf("%d", &n);
    for(int i = 1; i <= n; i++) std::scanf("%lld%lld", &p[i], &r[i]);
    std::printf("%lld\n", crt());
    return 0;
}

拓展中国剩余定理（exCRT）

与 CRT 不同，这次我们尝试两两合并方程。

考虑两个方程 x \equiv a_1 \pmod {b_1}，x \equiv a_2 \pmod {b_2}。

我们将它们转成不定方程：x = a_1 + b_1p = a_2 + b_2q，即 b_1p - b_2q = a_2 - a_1。

对于这个方程，我们用拓展欧几里得算出 p 和 q 的一组解。（如果 a_2 - a_1 不能被 \gcd(b1, b2) 整除则无解）

那么这两组方程的解为 x \equiv a_1 + b_1p = a_2 + b_2q \pmod {\operatorname{lcm}(b_1, b_2)}。

代码

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
LL excrt() {
    LL a1, b1, a2, b2, x, y;
    a1 = r[1], b1 = p[1];
    for(int i = 2; i <= n; i++) {
        a2 = r[i], b2 = p[i];
        if(a2 < a1) std::swap(a1, a2), std::swap(b1, b2);
        LL a = b1, b = b2, c = a2 - a1;
        LL g = exgcd(a, b, x, y);
        if(c % g) return -1;
        a /= g, b /= g, c /= g;
        b1 = lcm(b1, b2);
        y = y * (b1 - c) % b1;
        a1 = (a2 + b2 * y % b1) % b1;
    }
    return a1;
}

例题

洛谷 P4777

注意此题需要用前面的乘法技巧，因为可能会爆 long long。

#include <cstdio>
#include <algorithm>

typedef long long LL;

const int N = 1e5 + 5;

LL r[N], p[N];
int n;

LL gcd(LL x, LL y) { return y == 0 ? x : gcd(y, x % y); }
LL lcm(LL x, LL y) { return x / gcd(x, y) * y; }

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) { x = 1, y = 0; return a; }
    LL x_, y_;
    LL g = exgcd(b, a % b, x_, y_);
    x = y_;
    y = x_ - a / b * y_;
    return g;
}

LL mul(LL a, LL b, LL mod) { return (a * b - (LL)((long double)a / mod * b + 0.5) * mod + mod) % mod; }

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
LL excrt() {
    LL a1, b1, a2, b2, x, y;
    a1 = r[1], b1 = p[1];
    for(int i = 2; i <= n; i++) {
        a2 = r[i], b2 = p[i];
        if(a2 < a1) std::swap(a1, a2), std::swap(b1, b2);
        LL a = b1, b = b2, c = a2 - a1;
        LL g = exgcd(a, b, x, y);
        if(c % g) return -1;
        a /= g, b /= g, c /= g;
        b1 = lcm(b1, b2);
        y = mul(y, b1 - c, b1);
        a1 = (a2 + mul(b2, y, b1)) % b1;
    }
    return a1;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld%lld", &p[i], &r[i]);
    printf("%lld\n", excrt());
    return 0;
} /*
3
11 6
25 9
33 17
*/

小结

数论初步到这里就差不多了，看到这里说明你已经入门了。

后面的就等到数论进阶来讲吧。

完结撒花~