1. 从一道蓝桥杯真题说起为什么数论是算法竞赛的“硬通货”去年备赛蓝桥杯我遇到一道题大意是给定一个正整数n求1到n中所有与n互质的数的和。乍一看暴力枚举O(n log n)的复杂度对于n最大到10^9的数据范围直接超时。当时卡了很久直到我翻出欧拉函数的性质公式如果n 1那么1到n中与n互质的数之和为n * φ(n) / 2。这个结论直接让计算复杂度降到了O(sqrt(n))计算单个 φ(n) 的复杂度问题迎刃而解。这个经历让我深刻体会到在算法竞赛尤其是蓝桥杯中数论不是选修课而是决定你能否在有限时间内解决中高难度题目的“硬通货”。数论知识往往以“模板”的形式出现比如最大公约数、快速幂、欧拉函数。很多人觉得背下模板就行但一到比赛题目稍微变形或者需要组合多个知识点就无从下手。问题在于只记住了“怎么做”却不理解“为什么可以这么做”以及“什么时候该用”。这篇文章我就结合自己刷题和比赛的经验把蓝桥杯常考的几个核心数论模板——最大公约数、欧拉函数含线性筛法、快速幂、扩展欧几里得算法——掰开揉碎了讲清楚。我会重点讲清楚每个算法的底层逻辑、应用场景、代码实现中的易错点以及如何将它们串联起来解决复杂问题。目标不是罗列代码而是让你建立一套遇到数论问题时的思考框架。2. 最大公约数不止于“辗转”理解其计算本质与优化最大公约数恐怕是大多数人接触的第一个数论算法。gcd(a, b)表示能同时整除a和b的最大正整数。最经典的求法是欧几里得算法辗转相除法其代码简洁得令人发指int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }但这里有几个关键点需要深究。第一时间复杂度。很多人说它是O(log min(a, b))这是基于一个关键性质每经过一次递归较大的那个数至少减少一半。为什么呢考虑a b那么a % b的结果一定小于b。在最坏情况下比如斐波那契数列相邻项a % b约等于a - b但通过数学归纳可以证明每两步两个数中最大的那个至少减半从而保证了对数复杂度。在竞赛中对于a, b在10^9甚至10^18范围内这个算法都瞬间完成。第二关于边界和负数。上述代码假设输入是非负整数。如果存在负数公约数在数学上定义为正数所以我们需要取其绝对值。一个健壮的实现是return b 0 ? abs(a) : gcd(b, a % b);。此外当a和b都为0时最大公约数在数学上未定义通常视作0代码中gcd(0, 0)会返回0这需要根据题目上下文判断是否合理。第三std::gcd与二进制算法。C17 在numeric头文件中提供了std::gcd函数建议在允许的情况下直接使用避免手写错误。此外还有一种基于位运算的“二进制 GCD 算法”Stein算法它避免了耗时的取模运算通过位移和减法来操作尤其适合在高精度整数或没有硬件取模指令的环境下使用。其原理是利用了这些性质gcd(a, b) gcd(b, a)gcd(a, 0) agcd(2a, 2b) 2 * gcd(a, b)gcd(2a, b) gcd(a, b)若b为奇数。虽然在实际竞赛中普通的欧几里得算法完全够用但知道这种优化思路是有益的。注意在求解最小公倍数lcm(a, b)时务必使用公式a / gcd(a, b) * b来计算而不是a * b / gcd(a, b)。虽然数学上等价但后者先乘后除可能导致中间结果溢出即使最终结果在数据范围内。先除后乘是更安全的做法。3. 欧拉函数定义、求法与线性筛的降维打击欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。例如φ(8) 41, 3, 5, 7。它是数论中一个极其重要的函数在 RSA 加密、原根、模幂循环节等问题中都有核心应用。3.1 单点求值基于质因数分解的公式根据算术基本定理任何大于1的整数都可以唯一分解为质数的幂次积n p1^k1 * p2^k2 * ... * pm^km。欧拉函数有一个优美的计算公式φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)。这个公式直观理解就是从总数n中去掉所有能被p1整除的数占比1/p1再去掉所有能被p2整除的数……但这样会重复去掉同时是p1和p2倍数的数所以根据容斥原理最终公式是连乘形式。因此求单个φ(n)的算法就转化为对n进行质因数分解。int phi(int n) { int ans n; for (int i 2; i n / i; i) { // 试除法分解质因数 if (n % i 0) { ans ans / i * (i - 1); // 等价于 ans * (1 - 1/i)但避免浮点数 while (n % i 0) n / i; } } if (n 1) ans ans / n * (n - 1); // 处理最后一个大于 sqrt(n) 的质因子 return ans; }这里有一个非常重要的细节代码中ans ans / i * (i - 1)。为什么不写成ans * (1 - 1/i)因为1/i在整数除法中为0。我们利用ans初始为n每次遇到一个质因子i就从ans中剔除因子1/i即先除以i再乘以(i-1)。这样保证了整个计算过程都在整数域内进行没有精度损失。这个算法的时间复杂度是O(sqrt(n))对于单个查询已经足够高效。3.2 区间批量求值线性筛法的艺术与实现细节如果题目要求我们求出1到N所有数的欧拉函数值比如N10^6用上面的单点求法总复杂度是O(N*sqrt(N))无法接受。这时就需要用到基于线性筛法的批量求法复杂度O(N)。线性筛法欧拉筛本身是用于快速筛选质数的其核心思想是让每个合数只被其最小的质因子筛掉一次。我们可以在筛的过程中同步计算每个数的φ值。我们需要利用欧拉函数的几个递推性质如果p是质数φ(p) p - 1。如果p是质数且i % p 0即p是i的质因子那么φ(i * p) φ(i) * p。因为i已经包含了质因子p根据公式φ(n) n * Π(1 - 1/p)乘以p后n变成了n*p但质因子集合没变所以φ也直接乘以p。如果p是质数且i % p ! 0即p与i互质那么φ(i * p) φ(i) * (p - 1)。因为i和p互质满足积性函数性质φ(i*p) φ(i) * φ(p)而φ(p) p-1。基于这些性质我们可以在线性筛的框架下递推const int N 1000000; int primes[N], cnt; // 存储所有筛出来的质数 int phi[N]; // 存储每个数的欧拉函数值 bool st[N]; // 标记是否被筛掉 void get_eulers(int n) { phi[1] 1; // 定义 φ(1) 1 for (int i 2; i n; i) { if (!st[i]) { // i是质数 primes[cnt] i; phi[i] i - 1; // 性质1 } // 用当前已得到的质数 primes[j] 去筛掉 i * primes[j] for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; if (i % primes[j] 0) { // primes[j] 是 i 的最小质因子 phi[primes[j] * i] phi[i] * primes[j]; // 性质2 break; // 保证每个数只被最小质因子筛一次的关键 } else { // primes[j] 与 i 互质 phi[primes[j] * i] phi[i] * (primes[j] - 1); // 性质3 } } } }踩坑实录初始化phi[1] 1非常关键。虽然有些题目可能用不到φ(1)但如果不初始化当n1时未初始化的数组值可能导致错误。另外st数组和phi数组的大小要开够通常比最大值N多一点点防止边界溢出。线性筛求欧拉函数的妙处在于它把O(N log log N)的埃氏筛优化到了真正的O(N)并且同步得到了质数表和欧拉函数表一举两得。在蓝桥杯等竞赛中一旦遇到需要频繁查询欧拉函数或者与质数分布相关的题目预处理出phi数组往往是解题的关键第一步。4. 快速幂指数爆炸的克星与模运算的紧密结合快速幂算法解决的是计算a^k % p的问题其中a, k, p都是整数且k可能非常大比如10^9。直接循环乘k次复杂度O(k)显然不可行。快速幂的核心思想是二分降幂将复杂度降至O(log k)。其原理基于幂运算的结合律a^(2k) (a^k)^2a^(2k1) (a^k)^2 * a。我们可以将指数k用二进制表示。例如计算3^1313的二进制是1101那么3^13 3^(8) * 3^(4) * 3^(1)。我们发现这对应着二进制位为1的那些位。算法过程是初始化结果res 1底数base a % p先取模防止后续乘法溢出。然后循环检查k的二进制位当k 0时如果k的当前最低位是1即k 1那么res (res * base) % p接着无论该位是0还是1都要将底数平方以匹配下一个二进制位的权重即base (base * base) % p最后将k右移一位k 1。当k为0时循环结束res即为所求。int qmi(int a, int k, int p) { // 计算 a^k % p int res 1 % p; // 处理 p1 的特殊情况 while (k) { if (k 1) res (long long)res * a % p; // 当前二进制位为1乘入结果 a (long long)a * a % p; // 底数平方 k 1; // 指数右移 } return res; }这里有两个至关重要的细节。第一类型转换。res * a和a * a这两个乘法运算在a和p都是int范围内比如10^9时乘积可能超过int范围约2*10^9导致溢出。因此我们必须先将其中一个乘数转换为long long类型相乘后再对p取模最后结果转回int。这是快速幂实现中最常见的错误之一。第二初始化。res 1 % p是为了处理p 1的边界情况。当p 1时任何数模1都是0所以结果应为0。如果写成res 1那么当k0时任何数的0次方定义为1函数会返回1而1 % 1 0这就产生了矛盾。用1 % p初始化可以统一处理p1的情况保证a^0 % 1 0。快速幂的应用远不止于计算幂次。它是解决“模意义下的乘法逆元”的基础。什么是乘法逆元对于整数a和模数pp是质数如果存在整数x使得a * x ≡ 1 (mod p)则称x为a模p的逆元记作a^(-1)。根据费马小定理当p为质数且a不是p的倍数时a^(p-1) ≡ 1 (mod p)因此a * a^(p-2) ≡ 1 (mod p)。所以a模p的逆元就是a^(p-2) % p这直接用快速幂就能求出。在组合数学中计算C(n, m) % p组合数取模时逆元是必不可少的工具。5. 扩展欧几里得算法求解线性同余方程与乘法逆元扩展欧几里得算法是欧几里得算法的扩展。它不仅能求出a和b的最大公约数d还能找到一对整数x, y使得它们满足贝祖等式a*x b*y d。这个方程的解在求解线性同余方程、计算模逆元等问题中至关重要。5.1 算法原理与递归实现算法的推导基于递归。假设我们已经知道了gcd(b, a % b)的解x1, y1满足b * x1 (a % b) * y1 gcd(b, a % b) gcd(a, b) d。 我们知道a % b a - (a / b) * b这里/是整数除法。代入上式b * x1 (a - (a / b) * b) * y1 d a * y1 b * (x1 - (a / b) * y1) d对比原始等式a * x b * y d我们可以得到当前递归层解(x, y)与下一层解(x1, y1)的关系x y1y x1 - (a / b) * y1递归的边界条件是当b 0时此时gcd(a, 0) a等式a * x 0 * y a有一组显然的解x 1, y 0y可以是任意整数通常取0。// 函数返回值为 gcd(a, b)同时通过引用返回一组特解 x, y 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); // 注意这里交换了x和y的位置 y - a / b * x; return d; }代码中一个精妙之处在于递归调用exgcd(b, a % b, y, x)。我们交换了x和y的位置传入。这样在递归返回时上一层的y实际上接收了下层的x1上一层的x接收了下层的y1。然后我们执行y - a / b * x这里的y是上一层的y即下层的x1x是上一层的x即下层的y1。这行代码就等价于y x1 - (a/b)*y1。这种写法减少了中间变量让代码非常简洁。5.2 应用一求解线性同余方程线性同余方程形式为a * x ≡ b (mod m)。这意味着a*x - b是m的倍数即存在整数y使得a*x m*y b。这正好是扩展欧几里得算法能解决的方程形式。设d gcd(a, m)。方程a*x m*y b有整数解的充要条件是d能整除b。如果d ∤ b则方程无解。如果有解我们可以先用exgcd求出a*x0 m*y0 d的一组特解(x0, y0)。由于我们需要的是a*x m*y b的解将等式两边同时乘以b/d得到a * (x0 * b/d) m * (y0 * b/d) b。所以原方程的一个特解是x x0 * (b / d) % m。注意这里求出的x可能不在0到m-1范围内我们可以通过x (x % (m/d) (m/d)) % (m/d)将其调整到最小非负整数解。而且在模m意义下这个方程恰好有d个不同的解它们之间相差m/d。5.3 应用二求乘法逆元扩展欧几里得法前面提到当模数p为质数时可以用快速幂求逆元。如果模数m不是质数但a与m互质即gcd(a, m) 1我们仍然可以求a模m的逆元。此时逆元x满足a*x ≡ 1 (mod m)即a*x m*y 1。这正是扩展欧几里得算法可以求解的方程。调用exgcd(a, m, x, y)得到的x就是a模m的一个逆元可能需要调整到0~m-1范围内。这种方法比快速幂求逆元更通用。实操心得在竞赛中如果模数是质数优先用快速幂求逆元代码更短更快。如果模数非质数或者题目明确要求用扩展欧几里得再使用后者。务必注意使用扩展欧几里得求逆元的前提是gcd(a, m) 1否则逆元不存在。6. 模板整合与实战以蓝桥杯风格题目为例掌握了这些独立的模板后关键是要学会在复杂问题中识别并组合使用它们。我们来看一个综合性的例子它融合了最大公约数、快速幂和模运算。假设题目计算(a^b) mod m的值其中a, b, m均由另一个函数f(n)生成。f(n) gcd(n, φ(n)) * nφ是欧拉函数。a f(L), b f(R), m 998244353一个质数。L, R是给定的范围 (1 L R 10^6)。我们需要高效计算这个表达式。分析预处理由于L, R范围达到10^6我们需要用线性筛法O(N)预处理出1到N所有数的欧拉函数phi[i]。计算 f(n)根据定义f(n) gcd(n, phi[n]) * n。我们可以在预处理后用O(1)时间计算任意f(n)。计算 a 和 ba f(L),b f(R)。注意a和b可能非常大n最大10^6f(n)最大约10^12但还在long long范围内。计算 a^b mod m这里b可以非常大最大约10^12直接作为快速幂的指数输入。快速幂算法O(log b)可以轻松处理。模数 m998244353是质数这很友好我们求逆元等操作都可以用费马小定理快速幂。代码框架示意#include iostream using namespace std; typedef long long LL; const int N 1000010; const int MOD 998244353; int primes[N], phi[N], cnt; bool st[N]; LL f[N]; // 存储 f(i) // 线性筛求欧拉函数 phi[] void init() { 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); } } } // 计算 f(i) for (int i 1; i N; i) { f[i] (LL)gcd(i, phi[i]) * i; // 注意转换为LL防止溢出 } } // 快速幂模板 int qmi(LL a, LL k, int p) { int res 1 % p; a % p; // 先取模防止后面乘法溢出 while (k) { if (k 1) res (LL)res * a % p; a (LL)a * a % p; k 1; } return res; } int main() { init(); int L, R; cin L R; LL a f[L]; LL b f[R]; int ans qmi(a, b, MOD); cout ans endl; return 0; }这个例子展示了如何将多个模板串联预处理线性筛为后续O(1)查询提供支持最大公约数用于计算f(n)快速幂处理大指数取模。在竞赛中这种“预处理组合应用”的模式非常常见。7. 避坑指南与性能优化在实际编码和比赛中除了理解原理一些细节上的处理能让你避免很多不必要的失分。关于数据类型的选择这是数论题最隐蔽的坑。务必时刻警惕数据范围。当两个int相乘时结果可能溢出int。例如快速幂中的res * a即使a和res都小于模数pint范围内它们的乘积也可能超过2e9。解决方案在乘法前强制转换为long long。中间过程可能超出long long。如果模数p在int范围内但指数k极大比如10^18快速幂中的a在平方过程中可能达到(p-1)^2这仍在long long范围内~1e18。但如果p本身是long long范围如1e18那么平方就会溢出。此时需要使用“慢速乘”或__int128如果编译器支持。数组大小。线性筛需要O(N)的空间如果N10^7int数组大小约为40MB这在竞赛通常的256MB内存限制内是可以接受的。但开到10^8就需要400MB可能超限。估算内存是好习惯int数组长度N约占用4N字节。快速幂的递归与迭代上面给出的是迭代写法它比递归写法更节省栈空间且常数更小。递归写法虽然直观a^k (a^(k/2))^2 * [a]但在指数极大时可能导致栈溢出。一律建议使用迭代写法。扩展欧几里得的解不唯一算法求出的(x, y)只是一组特解。通解形式为x x0 (b/d)*t,y y0 - (a/d)*t其中t为任意整数。在求逆元或同余方程解时我们通常需要最小非负整数解。可以通过模运算调整x (x % (m/d) (m/d)) % (m/d)。欧拉筛中的break条件这是保证线性复杂度的关键。if (i % primes[j] 0) break;这行代码意味着当primes[j]是i的最小质因子时筛完i * primes[j]后就停止。因为对于后续更大的质因子primes[j1]i * primes[j1]的最小质因子应该是primes[j]因为primes[j]能整除i它应该在未来用i (i / primes[j]) * primes[j1]和primes[j]来筛这样才能保证每个合数只被筛一次。忘记break会导致算法退化为O(N log N)。最后我个人的体会是数论模板的代码量都不大但每一行都蕴含着深刻的数学原理。死记硬背代码不如理解其背后的数学变换和边界条件。在刷题时最好能自己从零推导一遍算法然后默写实现再对比标准模板查漏补缺。遇到涉及模运算的题目养成先估算数据范围、选择合适数据类型的习惯可以避免很多调试时间。把这些基础工具练到肌肉记忆的程度在赛场上你才能把更多精力放在更高层次的算法设计和问题分析上。
