1. 从“刷题”到“备赛”为什么你需要一份数论模板如果你正在准备蓝桥杯这类算法竞赛尤其是到了国赛阶段面对一道数论题脑子里第一时间蹦出来的是去搜索引擎里翻找“欧几里得算法怎么写”还是能立刻在本地IDE里调出一个经过自己千锤百炼、边界清晰的函数这个区别往往就是“会做”和“能在有限时间内做对”之间的鸿沟。我参加过不少比赛也带过一些学生发现很多同学在数论问题上失分不是因为不懂原理而是栽在了实现细节上。比如快速幂忘了处理指数为负数或零的情况筛素数时数组开小了或者没处理好1和2的边界求组合数时明明知道要用逆元但写出来的模逆元函数在模数非质数时直接崩掉。比赛时时间紧张心态一慌这些平时觉得“小问题”的地方就可能让你整道题功亏一篑。“第十二届_国赛蓝桥杯个人模板_数论篇”这个标题指向的正是解决这个痛点的核心方法构建你自己的、可靠的代码模板库。它不是一份死记硬背的答案而是一个经过你亲手编写、反复测试、并深刻理解其适用条件和边界的工具集合。当赛题出现“素数判定”、“公约数”、“同余方程”、“组合数取模”这些关键词时你能像从工具箱里取出扳手一样迅速、准确地调用对应的函数把精力集中在问题建模和逻辑设计上而不是纠结于基础函数的正确性。这份“个人模板”的价值在于“个人”二字。它记录了你对每个知识点的理解深度、你曾经踩过的坑、以及你为解决特定问题所做的优化。接下来我将结合国赛级别的考察重点拆解数论模板中必须涵盖的核心模块并分享我在实现这些模板时总结的经验、技巧和那些容易忽略的“坑点”。2. 模板基石质数筛法与高效判定数论问题往往从质数开始。蓝桥杯国赛题目中涉及质数的题目不仅要求会判断更要求能高效地生成一段区间内的所有质数或者对质因数进行分解。一个高效的筛法模板是数论工具箱里的第一块基石。2.1 埃拉托斯特尼筛法埃氏筛的优化实现埃氏筛的思想很简单从2开始将每个质数的倍数标记为合数。一个最朴素的实现时间复杂度是 O(n log log n)但对于较大的 n比如 10^7其常数和内存访问模式并不理想。一个常见的、未优化的陷阱实现// 不推荐效率低且isPrime[0]和isPrime[1]的处理不优雅 vectorbool isPrime(n1, true); for (int i 2; i n; i) { if (isPrime[i]) { for (int j 2 * i; j n; j i) { isPrime[j] false; } } }优化后的埃氏筛模板// 参数整数 n // 返回值一个布尔向量 isPrimeisPrime[i] 表示 i 是否为质数 (i 0) vectorbool sieveOfEratosthenes(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; // 0和1不是质数 for (int i 2; i * i n; i) { // 外层循环优化只需到 sqrt(n) if (isPrime[i]) { // 内层循环优化从 i*i 开始标记因为 2*i, 3*i, ..., (i-1)*i 已经被更小的质数标记过了 // 使用 long long 防止 i*i 溢出 for (long long j (long long)i * i; j n; j i) { isPrime[j] false; } } } return isPrime; }关键优化点与踩坑记录外层循环边界i * i n这是最重要的优化。如果一个数n是合数那么它必然有一个不大于sqrt(n)的质因子。因此标记合数的工作只需要用sqrt(n)以内的质数来完成即可。内层循环起始点j i * i对于质数i为什么从i*i开始标记考虑i52*510已经在i2时被标记3*515在i3时被标记4*520在i2时被标记过了因为4是2的倍数。所以所有小于i*i的i的倍数都已经被更小的质数筛选过了。这个优化减少了大量重复操作。数据类型溢出当n较大时例如接近 10^9虽然筛法可能不适用这么大i * i可能会超出int范围导致溢出为负数从而使循环条件错误。使用long long是安全的做法。vectorbool的特异性vectorbool是vector的一个特化版本它通常每个元素只占1个比特可以节省大量内存对于 n10^7用vectorbool约需 1.25MB而vectorchar需 10MB。但它的访问和赋值可能比普通vector慢一点且不能取地址。在竞赛中vectorbool用于筛法是标准且推荐的做法因为内存优势巨大。2.2 线性筛欧拉筛与质因数分解预处理埃氏筛已经足够应对大多数情况但它依然存在重复标记的问题例如合数30会被质数2、3、5各标记一次。线性筛或称欧拉筛保证了每个合数只被其最小质因子标记一次时间复杂度严格 O(n)。这在需要同时获取质数列表和每个数的最小质因子时特别有用。线性筛模板// 参数整数 n // 返回值primes - 存储所有 n 的质数 minFactor - 存储每个数的最小质因子质数的最小质因子是其本身。 pairvectorint, vectorint linearSieve(int n) { vectorint primes; vectorint minFactor(n 1, 0); // 0 表示尚未被筛到即质数或未处理 for (int i 2; i n; i) { if (minFactor[i] 0) { // i 是质数 minFactor[i] i; primes.push_back(i); } // 用当前已得到的质数 primes[j] 去筛 for (int j 0; j (int)primes.size(); j) { int p primes[j]; long long v (long long)i * p; if (v n) break; // 超过范围中断 minFactor[v] p; // 标记合数 v 的最小质因子为 p if (i % p 0) { // 关键如果 p 能整除 i那么对于更大的质数 primes[j1] // i * primes[j1] 的最小质因子应该是 p 而不是 primes[j1]。 // 这里中断保证了每个合数只被标记一次。 break; } } } return {primes, minFactor}; }为什么线性筛是线性的核心在于if (i % p 0) break;。这行代码保证了每个合数v i * p只会被其最小质因子p标记一次。举例假设i 4质数列表primes [2, 3]。j0:p2,v4*28标记minFactor[8]2。此时i % p 0(4%20)break。如果没有 break会继续j1:p3,v4*312标记minFactor[12]3。但12的最小质因子是2应该由i6 (6*2)时标记。这就造成了错误和重复。因为i4已经包含质因子2那么4*312这个数其最小质因子是2它应该在未来i6 (6*2)时被标记而不是现在。break 保证了这一点。线性筛的实战价值快速质因数分解有了minFactor数组我们可以用 O(log n) 的时间对一个数进行质因数分解这在需要多次分解的场景下如求欧拉函数、因子个数等是预处理利器。// 预处理 minFactor 数组后使用此函数进行质因数分解 // 参数x - 待分解的数 minFactor - 线性筛得到的最小质因子数组 // 返回值一个向量每个元素是一个 pair质因子, 指数 vectorpairint, int factorize(int x, const vectorint minFactor) { vectorpairint, int factors; while (x 1) { int p minFactor[x]; int cnt 0; while (x % p 0) { x / p; cnt; } factors.emplace_back(p, cnt); } return factors; }个人心得在蓝桥杯国赛环境中如果题目数据范围n在 10^7 量级且需要频繁查询质数或分解线性筛是更优选择。如果只是单次判断大量数字是否为质数埃氏筛更简单快捷。我通常会在模板里同时准备这两个函数根据题目特点选用。3. 同余与模运算快速幂与乘法逆元模运算是数论竞赛题的核心而快速幂是处理模指数运算的必备工具。它不仅用于计算a^b mod m更是理解乘法逆元、Miller-Rabin素数测试等高级算法的基础。3.1 快速幂模板与细节处理快速幂的核心思想是二分幂将指数b转化为二进制通过平方和乘法来加速计算。标准快速幂模板递归版与迭代版// 迭代版推荐无递归开销 // 参数底数 a, 指数 b, 模数 mod (如果不需要取模传入一个大于结果的值即可如 0x3f3f3f3f) // 返回值 a^b % mod long long quickPow(long long a, long long b, long long mod) { long long res 1 % mod; // 处理 mod1 的情况此时结果恒为0 a % mod; // 先取模防止 a*a 溢出 while (b 0) { if (b 1) { res (res * a) % mod; } a (a * a) % mod; b 1; } return res; } // 递归版便于理解 long long quickPowRecur(long long a, long long b, long long mod) { if (b 0) return 1 % mod; long long half quickPowRecur(a, b / 2, mod); long long res (half * half) % mod; if (b % 2 1) res (res * a) % mod; return res; }极易忽略的边界与坑点模数为1如果mod 1那么任何数对1取模结果都是0。模板中long long res 1 % mod;这行代码就优雅地处理了这种情况。如果写成res 1;当mod1且b0时会错误地返回1。底数先取模在循环开始前a % mod;是必要的。因为输入可能很大直接计算a*a会导致溢出即使a是long long。先取模可以保证中间结果在模数范围内。指数为负数标准的快速幂通常假设指数b为非负整数。如果题目涉及分数或负指数那通常是在求乘法逆元即a^(mod-2) mod mod费马小定理此时b是正数。所以模板一般不考虑负指数。数据类型使用long long是安全的。即使a和mod在int范围内a*a也可能超出int导致计算错误。3.2 乘法逆元费马小定理与扩展欧几里得在模运算中“除法”并不直接存在。我们需要用乘法逆元来实现(a / b) mod m的计算即找到一个x使得b * x ≡ 1 (mod m)那么a / b ≡ a * x (mod m)。逆元存在的充要条件是gcd(b, m) 1。方法一费马小定理要求模数 m 为质数如果m是质数且b不是m的倍数则b^(m-1) ≡ 1 (mod m)因此b的逆元inv(b) b^(m-2) mod m。直接用快速幂计算即可。// 费马小定理求逆元前提mod 是质数且 a 与 mod 互质。 long long invFermat(long long a, long long mod) { return quickPow(a, mod - 2, mod); }方法二扩展欧几里得算法通用方法求逆元本质是求解线性同余方程a * x ≡ 1 (mod m)即求解方程a*x m*y 1的整数解x。这正好是扩展欧几里得算法能解决的问题。// 扩展欧几里得算法 // 求解 ax by gcd(a, b) 的一组整数解 (x, y) // 返回值是 gcd(a, b) long long exGcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long d exGcd(b, a % b, y, x); // 递归注意交换 x, y y - (a / b) * x; return d; } // 使用扩展欧几里得求 a 在模 mod 下的逆元 // 返回值逆元如果逆元不存在即 gcd(a, mod) ! 1返回 -1或抛出异常 long long invExGcd(long long a, long long mod) { long long x, y; long long d exGcd(a, mod, x, y); if (d ! 1) { // 逆元不存在根据题目要求处理这里返回 -1 return -1; } // 调整 x 到 [0, mod) 范围内 return (x % mod mod) % mod; }两种方法的对比与选择费马小定理代码极其简单只需调用快速幂。但仅适用于模数为质数的情况。蓝桥杯很多题目模数会给出1e97这正是个质数所以费马小定理非常常用。扩展欧几里得适用范围更广只要a与mod互质即可不要求mod是质数。但代码稍复杂。实战建议在个人模板中我通常会同时实现这两种方法并写一个统一的接口函数。如果已知模数是质数如MOD 1000000007在代码里直接调用quickPow(a, MOD-2, MOD)更直观高效。如果模数不确定则使用扩展欧几里得版本。4. 组合数学与模运算组合数的高效计算组合数 C(n, m) 的计算是竞赛中的常客当 n 和 m 很大时直接计算阶乘会溢出必须结合模运算。这里介绍两种最实用的模板预处理阶乘逆元法适用于多次查询和 Lucas 定理适用于模数较小但 n, m 很大的情况。4.1 预处理阶乘与逆元模数为质数这是最常用、效率最高的方法。我们预处理出所有fact[i] i! % MOD和invFact[i] (i!)^-1 % MOD。那么C(n, m) fact[n] * invFact[m] % MOD * invFact[n-m] % MOD模板实现class Combination { private: vectorlong long fact, invFact; long long MOD; public: // 预处理 [0, maxN] 的阶乘和阶乘逆元 Combination(int maxN, long long mod) : MOD(mod) { fact.resize(maxN 1); invFact.resize(maxN 1); fact[0] 1; for (int i 1; i maxN; i) { fact[i] fact[i - 1] * i % MOD; } // 计算 maxN! 的逆元然后倒推所有阶乘的逆元 invFact[maxN] quickPow(fact[maxN], MOD - 2, MOD); // 费马小定理要求MOD是质数 for (int i maxN; i 1; --i) { invFact[i - 1] invFact[i] * i % MOD; } // 验证invFact[0] 应该是 1因为 0! 1。 } long long comb(int n, int m) { if (m 0 || m n) return 0; return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD; } // 排列数 A(n, m) n! / (n-m)! long long perm(int n, int m) { if (m 0 || m n) return 0; return fact[n] * invFact[n - m] % MOD; } }; // 使用示例 // const long long MOD 1e97; // Combination comb(1000000, MOD); // 预处理到 1e6 // long long ans comb.comb(n, m);关键点解析逆元的递推计算我们没有对每个invFact[i]单独用快速幂求逆那样是 O(N log MOD)。而是先求出invFact[maxN]然后利用关系invFact[i-1] invFact[i] * i % MOD线性递推回来。因为(i-1)!^-1 (i! * i^-1)^-1 i!^-1 * i。这个技巧将预处理复杂度降到了 O(N)。边界处理在comb函数中检查m是否在[0, n]范围内否则返回0这符合组合数定义。模数必须为质数这个模板基于费马小定理求逆元所以要求MOD是质数。常见的1e97和998244353都满足。4.2 Lucas 定理处理大组合数取模当n和m非常大比如 10^18但模数p是一个不太大的质数比如 10007时我们无法预处理到n的阶乘。此时需要使用 Lucas 定理。Lucas 定理对于质数p有C(n, m) % p C(n % p, m % p) * C(n/p, m/p) % p这实际上把大数的组合数计算分解为若干个小数的组合数计算。小数部分C(n%p, m%p)可以直接用预处理好的小范围阶乘来计算预处理到p-1即可而C(n/p, m/p)部分可以递归下去。Lucas 定理模板// 假设已经有一个预处理好的组合数类 Combination能处理 n, m P 的情况。 long long lucas(long long n, long long m, long long P, Combination comb) { if (m 0) return 1; // C(n, m) % P C(n%P, m%P) * Lucas(n/P, m/P, P) % P return (comb.comb(n % P, m % P) * lucas(n / P, m / P, P, comb)) % P; }使用场景与限制模数 p 必须是质数。p 不能太大因为我们需要预处理0!到(p-1)!的阶乘和逆元。如果p很大比如接近1e7预处理可能内存或时间不足。适用于n, m p的情况。如果n, m本身就小于p直接调用comb.comb(n, m)即可。个人踩坑记录我曾在一道题中看到模数p10007不大n, m在 10^9 级别兴冲冲地用了 Lucas 定理。但我忘记预处理Combination类而是在lucas函数里每次都去算阶乘和逆元导致超时。切记Combination对象应该全局初始化一次而不是每次调用都新建。模板的封装性很重要。5. 公约数与公倍数欧几里得与扩展应用最大公约数GCD和最小公倍数LCM是数论中最基础的概念相关算法欧几里得算法及其扩展形式必须做到信手拈来。5.1 欧几里得算法辗转相除法与最小公倍数求最大公约数的递归实现简洁优雅但需要注意递归深度。对于极端大的数如高精度数递归可能导致栈溢出但竞赛中的int64范围数据完全不用担心。GCD与LCM模板// 递归版本 long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } // 迭代版本避免递归开销推荐 long long gcdIterative(long long a, long long b) { while (b ! 0) { long long t a % b; a b; b t; } return a; } // 最小公倍数LCM(a, b) a / GCD(a, b) * b // 注意先除后乘防止 a*b 溢出 long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }一个关键细节lcm中的计算顺序一定要写成a / gcd(a, b) * b而不是a * b / gcd(a, b)。因为a*b可能会超出long long的范围例如a1e18, b1e18导致溢出。先做除法可以保证中间结果在可控范围内。5.2 扩展欧几里得算法ExGCD解线性方程与逆元我们在第3.2节已经见到了扩展欧几里得算法求逆元。这里再深入一下它的原理和应用。扩展欧几里得算法不仅求出gcd(a, b)还求出了一组整数解(x, y)满足裴蜀等式a*x b*y gcd(a, b)。算法递归式的理解假设我们已经知道了b*x1 (a % b)*y1 gcd(b, a % b) gcd(a, b)的解(x1, y1)。 由于a % b a - (a/b)*b代入上式b*x1 (a - (a/b)*b)*y1 gcd(a, b)整理得a*y1 b*(x1 - (a/b)*y1) gcd(a, b)所以原方程a*x b*y gcd(a, b)的一组解为x y1y x1 - (a/b) * y1这就是模板中exGcd(b, a % b, y, x);和y - (a / b) * x;的由来。递归到b0时gcd(a,0)a方程变为a*x 0*y a显然有一组解(1, 0)。扩展欧几里得的典型应用求解线性同余方程a*x ≡ c (mod m)。方程等价于a*x m*y c。设d gcd(a, m)。如果c % d ! 0则无解。否则先用 ExGCD 求出a*x0 m*y0 d的一组特解(x0, y0)。原方程的一组特解为x1 x0 * (c / d)。方程的通解为x x1 k * (m / d)k为任意整数。求乘法逆元如前所述是c1的特殊情况。求解二元一次不定方程直接应用。模板解线性同余方程// 求解 a*x ≡ b (mod m) // 返回值一个 pairbool, long long first 表示是否有解second 表示最小非负整数解如果无解则值无意义。 pairbool, long long solveLinearCongruence(long long a, long long b, long long m) { long long x, y; long long d exGcd(a, m, x, y); if (b % d ! 0) { return {false, 0}; // 无解 } // 特解 long long x0 x * (b / d) % m; // 最小非负整数解 long long t m / d; long long ans (x0 % t t) % t; return {true, ans}; }经验之谈扩展欧几里得算法是数论中的一个“瑞士军刀”理解其推导过程比死记代码更重要。在比赛中如果遇到“求关于x的同余方程”这类题目基本就是它的用武之地。我习惯把exGcd和solveLinearCongruence函数都放进模板前者是基础工具后者是直接可用的解决方案。6. 实战综合模板的组装与竞赛策略有了以上这些模块化的模板我们如何在实际比赛中运用这不仅仅是代码的堆砌更涉及到问题分析、模板选择和时间管理。6.1 识别题目中的数论“关键词”拿到一道题快速识别其数论本质能帮你迅速定位需要使用的模板“素数”、“质数”考虑质数筛埃氏筛/线性筛、Miller-Rabin素数测试国赛偶尔会考。“最大公约数”、“最小公倍数”直接使用gcd和lcm函数。可能涉及到多个数的GCD/LCM或者与数组、序列结合。“同余”、“模”大概率涉及模运算、快速幂、逆元。注意模数是否是质数以决定使用费马小定理还是扩展欧几里得求逆元。“组合数”、“排列数”、“方案数”使用组合数模板。注意数据范围决定用预处理阶乘法还是Lucas定理。“方程”、“解”可能是线性同余方程使用扩展欧几里得算法。“因子”、“因数”可能需要质因数分解利用线性筛得到的minFactor数组或者求约数个数、约数和。6.2 模板的封装与测试你的个人模板不应该是一堆散乱的函数。我推荐按模块组织在一个头文件里例如number_theory.h或者在一个类的静态方法中。更重要的是在备赛期间就要对每个模板函数进行充分的测试。测试用例设计思路边界测试输入为0、1、负数、大数、模数为1等。正确性测试用小数据暴力计算如组合数可以用定义计算来验证模板结果。性能测试对于筛法测试n1e7时的运行时间是否可接受通常应在1秒内。交互测试测试不同模板之间的协作例如用线性筛分解质因数再用结果去算欧拉函数。一个简单的测试框架可以帮你建立信心void testGCD() { assert(gcd(12, 18) 6); assert(gcd(0, 5) 5); assert(gcd(7, 0) 7); assert(gcd(-12, 18) 6); // 根据需要处理负数 cout GCD tests passed. endl; }6.3 比赛中的决策何时自己推导何时套用模板国赛时间宝贵但也不是所有题目都能一眼套模板。我的策略是前30分钟通读所有题目标记出明显是数论模板题的题目。这类题通常描述直接关键词明显可以规划在中段解决。对于复杂题目先尝试抽象出数学模型。如果分析后发现核心是求组合数模一个大质数那么直接套用预处理阶乘的模板如果发现需要解一个同余方程就套用solveLinearCongruence。警惕变种有些题目会包装一下比如通过“路径计数”考察组合数通过“循环节”考察模运算和扩展欧几里得。这时需要冷静分析将其还原为标准的数论问题。模板不匹配时如果题目条件与模板前提不符例如模数非质数但需要求逆元不要强行套用。需要回归数论基础寻找其他方法例如使用扩展欧几里得求逆元或者分解模数后用中国剩余定理CRT组合答案。中国剩余定理也是国赛可能涉及的进阶内容值得在模板中准备。关于中国剩余定理CRT的简单准备当需要求解一组同余方程x ≡ a_i (mod m_i)且m_i两两互质时可以使用CRT。虽然考频不如前述内容高但准备一个模板可以应对不时之需。// 扩展欧几里得求逆元用于CRT long long inv(ll a, ll m) { long long x, y; exGcd(a, m, x, y); return (x % m m) % m; } // 中国剩余定理 CRT解方程组 x ≡ a[i] (mod m[i]), m[i] 两两互质 long long crt(const vectorlong long a, const vectorlong long m) { long long M 1; for (auto mod : m) M * mod; long long res 0; for (size_t i 0; i a.size(); i) { long long Mi M / m[i]; long long invMi inv(Mi, m[i]); // 求 Mi 模 m[i] 的逆元 res (res a[i] * Mi % M * invMi % M) % M; } return res; }构建“第十二届_国赛蓝桥杯个人模板_数论篇”的过程是一个将知识内化为本能反应的过程。它不仅仅是代码的集合更是你对数论理解深度和解题熟练度的体现。在紧张的竞赛环境中一个经过反复锤炼、边界清晰的模板能为你节省大量时间并极大降低低级错误的概率。记住最好的模板是你自己写过、改过、错过的那个版本。