xiao9di 的博客
数论：从入门到精通（deepseek生成）
xiao9di LV 1 SU @ 2026-3-28 16:28:52

我和DS说了如下内容：

写一本适用于信奥学生的关于“数论“的书， 内容包括：质数，欧几里得算法，同余定理和模运算， 快速幂， 费马小定理和威尔逊定理， 扩展欧几里得算法， 乘法逆元， 欧拉函数和欧拉定义， 中国剩余定理，组合数取模， 容斥原理， 卢卡期定理， 矩阵快速幂， 大步小步算法与原根， 生成相关的目录， 每个章节详细解释相关的知识点， 并给出相关的算法题（更出在线提交地址， 出给可以AC的代码）。 生成一本PDF文件

然后就得到了下面的内容。

这是一份为信息学竞赛（OI）选手准备的数论教程的完整Markdown源码。

你可以将以下内容保存为 .md 文件（例如 Number_Theory_OI.md），然后使用支持LaTeX数学公式的编辑器（如Typora， VS Code + Markdown Preview Enhanced，或 Obsidian）打开预览。如果需要生成PDF，通常可以通过浏览器的“打印”功能（Ctrl+P -> 另存为PDF）或使用Pandoc工具进行转换。

由于内容较长，以下为书稿的完整结构及内容。

数论：从入门到精通

—— 信息学竞赛完全指南

前言在信息学竞赛（OI）中，数论是算法设计的基础，也是区分选手水平的关键模块。从简单的质数判定到复杂的同余方程组，数论不仅考察数学思维，更考验代码实现能力。本书旨在系统性地讲解数论核心知识点，结合经典习题与AC代码，帮助读者构建完整的数论知识体系。

第一章质数

1.1 质数的判定

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

试除法：判断 $n$ 是否为质数，只需枚举 $2$ 到 $\sqrt{n}$ 的整数。时间复杂度 $O(\sqrt{n})$ 。

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++) { // 避免 i*i 溢出
        if (n % i == 0) return false;
    }
    return true;
}

1.2 质数筛法

埃拉托斯特尼筛法

原理：从小到大枚举质数，筛去其倍数。时间复杂度 $O(n \log \log n)$ 。

const int N = 1e6;
bool isPrime[N+1];
void sieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

欧拉筛（线性筛）

保证每个合数只被其最小质因子筛掉一次，时间复杂度 $O(n)$ 。

int primes[N], cnt;
bool st[N];
void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

1.3 质因数分解

算术基本定理：任何大于1的自然数都可以唯一分解为有限个质数的乘积。

试除法分解：

vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> res;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            res.push_back({i, cnt});
        }
    }
    if (n > 1) res.push_back({n, 1});
    return res;
}

练习题：

第二章欧几里得算法

2.1 最大公约数

欧几里得算法（辗转相除法）： [ \gcd(a, b) = \gcd(b, a \bmod b) ]

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

2.2 最小公倍数

[ \mathrm{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} ] 注意计算时先除后乘，防止溢出。

练习题：

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

第三章同余定理与模运算

3.1 同余的定义

若 $a \bmod m = b \bmod m$ ，则称 $a \equiv b \pmod{m}$ 。

3.2 模运算的性质

加法：$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
减法：$(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$
乘法：$(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$

注意：除法不直接满足模运算，需要用到乘法逆元。

第四章快速幂

快速幂用于在 $O(\log k)$ 的时间内计算 $a^k \bmod p$ 。

4.1 算法原理

将指数 $k$ 视为二进制，利用 $a^{2^i}$ 的递推关系。

long long qpow(long long a, long long k, long long p) {
    long long res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

练习题：

P1226 【模板】快速幂

第五章费马小定理与威尔逊定理

5.1 费马小定理

若 $p$ 为质数，且 $\gcd(a, p) = 1$ ，则： [ a^{p-1} \equiv 1 \pmod{p} ] 常用于求模逆元。

5.2 威尔逊定理

[ (p-1)! \equiv -1 \pmod{p} ] 当且仅当 $p$ 是质数。

练习题：

P1313 [NOIP2011 提高组] 计算系数（结合二项式定理）

第六章扩展欧几里得算法

6.1 裴蜀定理

对于任意整数 $a, b$ ，存在整数 $x, y$ 使得： [ ax + by = \gcd(a, b) ]

6.2 算法实现

扩展欧几里得算法求解 $ax + by = \gcd(a, b)$ 的一组特解。

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

练习题：

P1082 [NOIP2012 提高组] 同余方程

第七章乘法逆元

7.1 逆元的定义

若 $a \times x \equiv 1 \pmod{m}$ ，则 $x$ 是 $a$ 在模 $m$ 下的逆元，记作 $a^{-1}$ 。

7.2 求逆元的方法

费马小定理（模数为质数）： $a^{-1} \equiv a^{p-2} \pmod{p}$
扩展欧几里得（模数非质数也可用）：解方程 $ax + my = 1$
线性递推（求 $1 \dots n$ 的逆元）： [ inv[i] = (p - p/i) \times inv[p % i] % p ]

inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

练习题：

P3811 【模板】乘法逆元

第八章欧拉函数

8.1 欧拉函数的定义

$\varphi(n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数个数。

8.2 欧拉函数的性质

若 $n = p^k$ （ $p$ 为质数），则 $\varphi(n) = p^k - p^{k-1}$
积性函数：若 $\gcd(a, b) = 1$ ，则 $\varphi(ab) = \varphi(a) \varphi(b)$
欧拉定理：若 $\gcd(a, m) = 1$ ，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$

8.3 求欧拉函数

利用质因数分解：

int phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

练习题：

P2158 [SDOI2008] 仪仗队

第九章中国剩余定理

9.1 问题描述

求解同余方程组： [ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_n \pmod{m_n} \end{cases} ] 其中 $m_i$ 两两互质。

9.2 算法流程

令 $M = \prod m_i$ ， $M_i = M / m_i$ ， $t_i = M_i^{-1} \pmod{m_i}$ ，则： [ x = \sum a_i M_i t_i \pmod{M} ]

long long crt(int n, long long a[], long long m[]) {
    long long M = 1, res = 0;
    for (int i = 0; i < n; i++) M *= m[i];
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];
        long long inv, y;
        exgcd(Mi, m[i], inv, y);
        res = (res + a[i] * Mi % M * (inv % M + M) % M) % M;
    }
    return res;
}

9.3 拓展中国剩余定理（模数不互质）

使用合并法，将两个方程逐步合并。

练习题：

第十章组合数取模

10.1 预处理阶乘与逆元

当 $n, m$ 较小或模数为质数时：

const int N = 1e6, MOD = 1e9+7;
long long fac[N], invfac[N];

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % MOD;
    invfac[N-1] = qpow(fac[N-1], MOD-2, MOD);
    for (int i = N-2; i >= 0; i--) invfac[i] = invfac[i+1] * (i+1) % MOD;
}

long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * invfac[m] % MOD * invfac[n-m] % MOD;
}

练习题：

P1313 [NOIP2011 提高组] 计算系数

第十一章容斥原理

11.1 原理

对于有限集合 $A_1, A_2, \dots, A_n$ ： [ \left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}| ]

在数论中常用于求解与互质、倍数相关的问题。

练习题：

P3197 [HNOI2008] 越狱（补集转化）
P1450 [HAOI2008] 硬币购物（完全背包+容斥）

第十二章卢卡斯定理

12.1 定理内容

对于质数 $p$ ，将 $n, m$ 表示为 $p$ 进制： [ C_n^m \equiv \prod C_{n_i}^{m_i} \pmod{p} ] 其中 $n_i, m_i$ 是 $n, m$ 在 $p$ 进制下的各位数字。

12.2 算法实现

当 $p$ 较小且 $n, m$ 很大时使用。

long long lucas(long long n, long long m, long long p) {
    if (m == 0) return 1;
    return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

练习题：

P3807 【模板】卢卡斯定理

第十三章矩阵快速幂

13.1 矩阵乘法

用于加速线性递推，如斐波那契数列。

13.2 算法模板

struct Matrix {
    long long a[2][2];
    Matrix() { memset(a, 0, sizeof a); }
    Matrix operator*(const Matrix &b) const {
        Matrix res;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
        return res;
    }
};

Matrix mat_qpow(Matrix a, long long k) {
    Matrix res;
    res.a[0][0] = res.a[1][1] = 1; // 单位矩阵
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}

练习题：

第十四章大步小步算法与原根

14.1 离散对数问题

求解 $a^x \equiv b \pmod{p}$ （ $p$ 为质数）。

14.2 BSGS 算法

令 $x = i \cdot m - j$ ，其中 $m = \lceil \sqrt{p} \rceil$ ，转化为： [ a^{i \cdot m} \equiv b \cdot a^j \pmod{p} ] 用哈希表存储 $b \cdot a^j$ 的值。

long long bsgs(long long a, long long b, long long p) {
    a %= p, b %= p;
    if (b == 1) return 0;
    map<long long, int> mp;
    long long m = sqrt(p) + 1, cur = b;
    for (int j = 0; j < m; j++) {
        mp[cur] = j;
        cur = cur * a % p;
    }
    long long am = qpow(a, m, p), now = am;
    for (int i = 1; i <= m; i++) {
        if (mp.count(now)) return i * m - mp[now];
        now = now * am % p;
    }
    return -1; // 无解
}

14.3 原根

原根是模 $m$ 下阶为 $\varphi(m)$ 的数。通常从 $2$ 开始枚举，验证 $g^{\varphi(m)/q} \not\equiv 1$ 对每个质因子 $q$ 。

练习题：

附录

A. 常用模数

$10^9+7$
$998244353$

B. 常见技巧

防溢出：乘法使用 (a * b) % p 前若数值较大，可用 __int128 或快速乘。
负数取模：(x % p + p) % p。

结束语 数论的世界博大精深，掌握以上知识点足以应对大部分OI竞赛中的数论问题。希望读者在理解原理的基础上，多动手实践，将理论转化为代码能力。

生成PDF的说明

保存文件：将以上内容复制到一个文本编辑器中，保存为 Number_Theory_OI.md。
使用Typora：
- 打开Typora，导入该Markdown文件。
- 点击 文件 -> 导出 -> PDF。
使用VS Code：
- 安装 Markdown Preview Enhanced 插件。
- 右键预览页面，选择 Chrome (Puppeteer) -> PDF。

使用Pandoc命令行（需要安装LaTeX）：

pandoc Number_Theory_OI.md -o Number_Theory_OI.pdf --pdf-engine=xelatex -V mainfont="SimHei" -V geometry:margin=1in