企业官网建设流程全解析

如果你在算法竞赛里被数论题虐过，大概率见过这两样东西：一本被大家叫做“紫薯”的紫色封面算法书，一个圈内默认必刷的数论基础专题。把“紫薯第10章数学”和“专题14数论基础”放在一起学，是我见过最扎实的数论入门路径。这篇文章不打算复述书里的公式，而是把我在啃完这套组合后的整个思考过程、代码细节和踩坑记录梳理出来，给正准备硬啃这块骨头的朋友做一个参考。

1. 这套组合到底解决什么问题

1.1 数论是竞赛里最容易被放弃的板块

很多学算法的人对图论、动态规划都能聊几句，一提到数论就摇头。原因很现实：数论题很少给你一个可以直接套的模板，它考察的是你对数字本质的理解。你可以在完全不懂原理的情况下背熟一个最短路板子，但数论题做不到，因为同一道题稍微改一下数据范围，算法就得换一个层次。

但数论在竞赛里的占比一点都不低。无论是网络赛、区域赛还是校内选拔，质数、同余、欧拉函数、组合数取模都是高频考点。哪怕不考纯数论题，很多动态规划、概率期望、数据结构题在后半段也会突然冒出一个“对 1e9+7 取模”，这里的模运算、逆元、组合数都是数论基础。换句话说，数论不是一门可以跳过的选修课，它是支撑很多其他算法的基础设施。

我自己最早的时候也走过弯路：先去背了一堆公式，见到题就翻笔记，结果换个条件就不会了。后来发现问题的根源不是笨，而是知识没有形成结构。书上的定理和题集里的题目是两套语言，中间缺了一座桥。后来我把“紫薯第10章数学”和专题14数论基础结合起来学，才终于把零散的知识点串成了一条线。

1.2 紫薯讲原理，专题练代码

两套资料的分工非常清晰。“紫薯”第10章数学负责讲原理，它从质数、约数、同余开始，一步一步把定理推给你看，连为什么要有欧拉函数、为什么中国剩余定理长成那样都交代得明明白白。专题14数论基础则负责给题目，它按知识点把常见题型排好，让你把刚学的定理放到真实题目里验证。

我的配合方法很笨但很有效：每看一章紫薯，先把书里的模板代码抄一遍，手推一个小例子确认自己理解，然后去专题14里找对应知识点的题目做。看书看到的是“原来如此”，做题感受到的是“卧槽这里居然要这样转化”，两者缺一不可。只看书不去做题，你会觉得自己全会了，一合上书大脑空白；只刷题不看书，你会一直停留在“这题我见过，但是换个问法就没思路”的阶段。

如果你是第一次接触这套组合，建议按下面的节奏来：先花一周把紫薯第10章的质数、约数、同余三节读完，再把专题14里对应的基础题刷掉，不用贪多，每天一到两题就够。数论最重要的不是题量，而是每个结论你都能用自己的话解释清楚。

2. 核心知识点拆解与代码细节

2.1 线性筛法：一份代码解决筛素数和其他一堆事

先说最基础的质数筛。埃氏筛很好理解，复杂度是 O(n log log n)，在 n 到 1e7 的范围内完全够用。但专题14里很多题会顺带要你求欧拉函数、莫比乌斯函数，这时候线性筛才是正解。它的核心思想是：每个合数只被它的最小质因数筛掉一次。

const int N = 1000005; int primes[N], cnt; bool st[N]; void get_primes(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; } } }

注意循环里的判断条件primes[j] <= n / i，写成乘法primes[j] * i <= n容易溢出，虽然 int 乘 int 在大部分题目里不至于出事，但这个习惯建议一开始就养好。更关键的是if (i % primes[j] == 0) break;这行，它保证了每个合数只会被最小质因数访问到，所以总复杂度是 O(n)。

我见过不少初学者问：埃氏筛那么短，为什么要背线性筛？因为在很多数论题里，筛的过程不只是为了得到质数列表，还要顺便维护其他信息。比如筛欧拉函数时，if (i % primes[j] == 0)的判断就是区分两种状态的关键分支。一旦你理解了这行的意义，后面搞懂线性筛求欧拉函数、莫比乌斯函数就是水到渠成的事。

另外提醒一句：区间筛是专题14里的常客。当你要筛 [L, R] 范围内的质数，而 L 和 R 非常大但 R-L 很小，就不能直接开 1e9 的数组。这时只需要用 [2, sqrt(R)] 的质数去标记 [L, R] 的合数。这个是埃氏筛的扩展，跟线性筛的代码不太一样，建议亲手实现一次再做题。

2.2 欧拉函数：从定义到线性筛预处理

欧拉函数 φ(n) 表示 1 到 n 中与 n 互质的整数个数。它有一个通式：n 质因数分解为 p1^a1 * p2^a2 * ... 后，φ(n) = n * Π(1 - 1/pi)，等价于 n * Π((pi - 1) / pi)。

单点求欧拉函数用试除法就够了：

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; }

注意res = res / i * (i - 1)这个顺序。如果先乘再除，当 n 接近 1e9 且 i 很小时，res 可能就在中间过程溢出了，先除再乘几乎不影响精度还能防溢出。这个写法上的小心思，是很多老选手踩过坑之后总结出来的。

专题14里经常出现的是批量求欧拉函数，比如求 1 到 n 所有数的欧拉函数之和。这个用线性筛可以做到 O(n)：

const int N = 1000010; int phi[N], primes[N], cnt; bool st[N]; void get_phi(int n) { phi[1] = 1; for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt++] = i; phi[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] * i] = true; if (i % primes[j] == 0) { phi[primes[j] * i] = phi[i] * primes[j]; break; } else { phi[primes[j] * i] = phi[i] * (primes[j] - 1); } } } }

解释一下两个分支：当 i 已经被 primes[j] 整除，说明 primes[j] 是 i 的最小质因数，那么 primes[j]*i 相比 i 只是多乘了一个质因子，欧拉函数总体乘上 primes[j]；当 i 不被 primes[j] 整除，说明 primes[j] 是新增的质因子，欧拉函数要乘上 (primes[j] - 1)。这两个分支就是线性筛求欧拉函数的灵魂。

欧拉函数最重要的副产品是欧拉定理：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。当 n 是质数 p 时，φ(p) = p - 1，就得到费马小定理 a^(p-1) ≡ 1 (mod p)。这条定理是后面求逆元的理论根基，专题14里大量题都离不开它。

2.3 扩展欧几里得：一次递归把不定方程和逆元全搞定

扩展欧几里得几乎是数论基础专题里最常考的核心。它能用来解 ax + by = gcd(a, b) 的整数解，也可以用来求逆元、解同余方程。代码短，但很多人是背下来的，不知道递归到底发生了什么：

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

递归退出条件是 b = 0，此时 gcd = a，显然有一组解 x = 1, y = 0。回溯时，递归返回的是满足 bx + (a % b)y = gcd(b, a % b) 的一组解，我们通过交换参数让新 x 等于原来的 y，再更新y -= a / b * x，就得到了满足 ax + by = gcd(a, b) 的解。

我不知道你第一次看到这段代码是什么感觉，反正我当时盯着看了半小时才转过弯。我的建议是拿 a=6, b=4 手推一遍递归过程，把每层 x、y 的值写在纸上，写完之后你会彻底理解为什么参数在递归里是被交换的。

有了 exgcd 之后，求逆元就很直接了。要求 a 在模 m 意义下的逆元，相当于解 ax + my = 1，前提是 gcd(a, m) = 1。调用exgcd(a, m, x, y)后，x 就是逆元，最后对 m 取正：

int inv(int a, int m) { int x, y; int d = exgcd(a, m, x, y); if (d != 1) return -1; // 逆元不存在 return (x % m + m) % m; }

解一般同余方程 ax ≡ b (mod m) 也是这个套路：先求 g = gcd(a, m)，如果 b 不能被 g 整除就无解，否则两边同时除以 g，用 exgcd 求新方程的一组解，再乘倍数取模。专题14里很多题表面问的是“求最小正整数解”，实际考的就是这个流程。

2.4 中国剩余定理：同余方程组的联立解法

中国剩余定理解决的是模数两两互质的一组同余方程：

x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)

设 M = m1 * m2 * ... * mk，Mi = M / mi，则 x ≡ Σ ai * Mi * inv(Mi, mi) (mod M)。其中 inv(Mi, mi) 是 Mi 在模 mi 下的逆元，要用 exgcd 求。实现如下：

int crt(vector<int> a, vector<int> m) { int M = 1; for (int x : m) M *= x; int res = 0; for (int i = 0; i < a.size(); i++) { int Mi = M / m[i]; res += a[i] * Mi % M * inv(Mi, m[i]) % M; res %= M; } return (res + M) % M; }

这里面最容易出错的是每个乘法都要取模。a[i]、Mi、逆元这三个数在乘起来之前可能都小于 1e9，但乘完就爆 int，所以每步都要模。如果题目里的模数是两两不互质的，基础 CRT 不成立，需要改成扩展中国剩余定理，思路是把方程两两合并：x ≡ a1 (mod m1) 和 x ≡ a2 (mod m2) 联立成 x ≡ a1 + m1 * t (mod lcm(m1, m2))，这个合并过程又需要 exgcd。

建议先把基础版练熟，再去碰不互质的情况。我在专题14里遇到过几道不互质版 CRT，第一次做的时候完全没头绪，后来发现就是用 exgcd 合并方程，跟基础版没有本质区别，只是代码里多一个 gcd 判断分支。

2.5 快速幂：从矩阵到取模处处要用

在开始做题之前，建议把快速幂的板子也准备好。它和逆元、组合数取模、费马小定理强绑定，几乎每场竞赛都会用到。

int qpow(int a, int b, int mod) { int res = 1 % mod; while (b) { if (b & 1) res = 1LL * res * a % mod; a = 1LL * a * a % mod; b >>= 1; } return res; }

这里有个不起眼的细节：res = 1 % mod而不是直接res = 1，因为当 mod = 1 时幂运算结果应该为 0，否则会返回 1 导致边界 WA。这个坑我真实踩过，是在做一道模数为 1 的变态数据时挂掉的。

还有乘法溢出问题。用1LL * res * a在模数小于 1e9 时没问题，但模数一旦接近 1e18，两个 long long 相乘就会溢出。这种时候需要把快速幂里的乘法替换成“快速乘”，本质上是一个二进制拆分的加法，代码逻辑和快速幂几乎一样。专题14里有些题模数很大，建议提前写好这个函数备用。

3. 专题14刷题实操：顺序、套路和复盘方法

3.1 按“知识块”刷，而不是按题号硬刷

专题14的题量不小，如果从头到尾按顺序硬刷，很容易在前面几道偏数学证明的题上卡太久，心态会崩。我个人的建议是把它按知识块拆成几组，每一组内集中刷完再进下一组：

每组题目之间并不孤立。比如求逆元那组会用到 exgcd 和费马小定理，组合数取模那组又会用到快速幂和逆元。按块刷的好处是，你刷完一组之后能立刻知道这类题长什么样，建立“知识点到题型”的映射。

做每道题之前，我给自己定了一条规矩：至少独立思考 30 分钟。30 分钟不是死规定，但如果一道题我连一点思路都没有，说明问题不是“没灵感”，而是这个知识点还没有真正理解，这时候看题解是最高效的。看题解之后一定要合上题解，自己重新写一遍代码，不能边看边抄，否则下次碰到还是不会。

3.2 拿一道典型题走一遍完整流程

拿“求 a 关于模 n 的乘法逆元”这道最经典的题举例。看到题目第一反应应该是列式子：找一个 x 使得 ax ≡ 1 (mod n)。

如果你只知道暴力，就会枚举 x 从 1 到 n-1，复杂度 O(n)。当 a 和 n 到 1e9 级别时直接超时。这时候开始想：同余方程 ax ≡ 1 (mod n) 等价于 ax + ny = 1，这是一个标准的二元一次方程。从数学上想，只有当 gcd(a, n) = 1 时才有解，这正好是逆元存在的条件。

于是进入 exgcd 套路：调用exgcd(a, n, x, y)，得到一组特解，再把它调整成最小正整数解(x % n + n) % n。整个过程的三步——建立同余方程、判断 gcd、调用 exgcd——就是专题14里所有逆元题的标准路径。

我自己做这类题时的复盘笔记长这样：知识点是 exgcd 求逆元，卡住的环节是忘记对 gcd 判断非 1 时无解，题解里的关键转化是“同余方程改写成不定方程”，下次遇到同余问题先想能不能转成 ax + by = c 的形式。这种复盘不复杂，但能让你把每道题的收获留在脑子里，而不是刷完就忘。

3.3 整理一份“数论错题本”的方法

刷题很容易陷入“AC 了就是会了”的错觉。数论题尤其需要错题本，因为它的错法非常集中：有人总在取模上爆负数，有人把费马小定理用在非质数模数上，有人 CRT 忘记乘逆元。这些错第一次犯很正常，第二次再犯就是亏。

我的错题本只要四列：

错题本不用写得很长，重点是记录“为什么当时没想出来”。很多数论题不是你不会定理，而是没识别出该用哪条定理。把这些识别信号记下来，比重复刷十道题有用得多。

4. 常见问题与排查技巧

4.1 取模负数与溢出

C++ 里负数取模的结果是负的，比如-5 % 3 = -2。很多数论题求的是最小正整数解，最后如果不处理负数就 WA。统一格式：

int mod(int x, int m) { return (x % m + m) % m; }

这个(x % m + m) % m是处理负数的标准写法，适用于所有需要把结果归到 [0, m) 区间的场景。

溢出的场景更隐蔽。假设两个小于 1e9 的数相乘，int 直接溢出；long long 在大多数情况下够用，但模数接近 1e18 时就危险。除了用__int128硬扛，更通用的写法是快速乘：

long long mul_mod(long long a, long long b, long long mod) { long long res = 0; while (b) { if (b & 1) res = (res + a) % mod; a = (a * 2) % mod; b >>= 1; } return res; }

不要觉得这种写法慢，它在模数超过 int 范围的题里就是保命符。我一般把快速乘和快速幂放一起封装，用的时候直接换。

4.2 用错逆元求法

求逆元有三种主流方法，很多人一开始只会一种，遇到特殊场景就卡住。这里直接对比：

不少人一上来看到qpow(a, mod-2, mod)就直接背下来，但没意识到这里用到了费马小定理，前提条件是 mod 必须是质数。如果题目里模数是 1000000007 这种固定大质数，没问题；一旦模数是输入的变量，就必须改成 exgcd 或者先判断质数。专题14里至少有一道题专门卡这个点，我当时连续 WA 了三次才发现模数根本不是质数。

4.3 边界条件反复挂

数论题的边界值看着简单但特别容易挂。我整理了一个每次提交前默念的清单：

• n = 1 时，欧拉函数是 1，素数列表为空，很多筛法没初始化会出问题。
• 快速幂指数为 0 时，结果应该是 1 mod p，当 p = 1 时为 0。
• CRT 算出来的解可能是负数，记得最后取正。
• 区间筛中 L = 1 时，1 不是质数，要单独标记为合数。
• 求约数个数时，注意 n = p^a 这种只有一个质因子的情况，公式里的加一别漏。

这些边界不是靠智商规避的，是踩坑踩出来的。第一次做数论题就把这些情况全部标进错题本，后面会省下大量调试时间。

4.4 调试数论题的对拍技巧

数论题特别适合对拍，因为暴力解通常都很容易写。比如验证欧拉函数单点求法的正确性，可以写一个 O(n) 的暴力去数互质个数，然后拿它和正式代码跑同一个小数据。我自己常用 Python 或者 C++ 做个对拍脚本，随机生成 n，比较两边的输出，出错立刻定位。

对拍脚本的次要作用，是能帮你发现一些平时根本不会想到的输入。比如生成 n = 1000000007 这种大质数，或者 n = 2^30 这种 2 的幂，跑一遍就能看出代码在幂运算、边界上的小毛病。学习数论的过程中，对拍是性价比最高的调试方式，强烈建议每个人都熟练掌握。

5. 刷完数论基础之后还能往哪走

5.1 莫比乌斯反演：从基础到计数的下一步

刷完专题14之后，我想推荐的下一个方向是莫比乌斯反演。它和欧拉函数、线性筛强相关：用线性筛可以在 O(n) 内求出莫比乌斯函数 mu，然后通过容斥原理解决形如“1 到 n 中与 m 互质的数有多少个”的计数问题。

最开始看莫比乌斯反演会觉得是一堆玄学公式，但实际上它可以理解成在因数结构上做容斥。专题14里已经有几道题在雏形上沾到了莫比乌斯函数的边，比如统计 gcd 为 1 的数对数量。先把线性筛求 mu 的代码写出来，再去理解反演公式，会顺畅很多。

5.2 数论分块：O(n) 变 O(sqrt(n))

另一件值得学的事是数论分块。它解决形如 Σ floor(n/i) 的求和，i 从 1 到 n。直接累加是 O(n)，对大数据直接超时，但你会发现 floor(n/i) 的取值是一段一段相同的，每一段可以一起算，总复杂度降到 O(sqrt(n))。

这个技巧在后面的除数函数求和、莫比乌斯计数题中出现频率极高，而且代码短到不可思议。我会建议在刷完专题14后花一个下午专门练数论分块，它几乎是数论进阶里最“性价比高”的算法。

5.3 再往后：离散对数、原根、NTT

如果还想继续往上走，方向不外乎这几个：离散对数算法、阶与原根、二次剩余、多项式相关的数论变换。这些都是专题14的延伸，比如离散对数问题本质上是在群里求指数，和快速幂是反向操作；NTT 则是把数论取模和多项式卷积结合的大型考点。

但说实话，这些内容不需要在没刷完基础之前去碰。数论基础就像一个房子的地基，房子的样子可以是任意风格，但地基不牢固，后面学什么都摇摇晃晃。先把专题14踏踏实实刷完，让线性筛、欧拉函数、exgcd、CRT 这几根柱子立稳，再往上层加东西，那才是效率最高的路线。

我自己的实际体会是：数论不是靠背公式能学好的，一定要亲手推几个例子。专题14刷到一半的时候，我才真正理解 exgcd 递归返回的 x 和 y 是怎么一路被“换”回来的，那一刻的感觉比 AC 一道难题还舒爽。这篇文章里写出来的坑，我基本都踩过一轮，希望你能绕开，更快走到顿悟的节点。