1. 项目概述为什么我们需要一份“国赛级”的数论模板如果你参加过蓝桥杯尤其是国赛你肯定有过这样的体验赛场上时间一分一秒地流逝你读到了一道数论题。思路瞬间清晰你甚至能立刻在脑海里勾勒出代码框架。但当你开始敲键盘时却卡在了一个最基础的地方——快速幂的取模写错了欧拉筛的数组开小了还是扩展欧几里得求逆元的符号处理出了问题这些本应是“肌肉记忆”的基础代码在高压环境下却成了最不稳定的因素消耗着宝贵的调试时间甚至可能导致整道题目的崩盘。这正是我整理这份“第十二届国赛蓝桥杯个人模板_数论篇”的初衷。它不是一个简单的代码合集而是一套经过国赛强度检验的、高度工程化的“武器库”。这里的每一行代码都源自真实的解题场景尤其是那些时间紧迫、需要一次写对的场合。数论作为算法竞赛中逻辑最严密、代码最精炼但也最容易出错的板块之一其模板的可靠性直接决定了你能不能在关键时刻“一发入魂”。这份模板的核心价值在于“实战化”和“完整性”。它不仅仅实现了算法更封装了常见的调用模式和边界处理。例如素数筛法不仅给出埃氏筛和欧拉筛还会明确在数据规模达到10^7时该用哪个、数组该开多大、如何兼顾速度与内存同余运算部分会直接给出快速幂、乘法逆元、同余方程求解的连贯操作链。我们的目标是当你在比赛中识别出题目属于某个数论模型时可以像调用标准库函数一样自信地复制粘贴对应的模板段并确信它能在给定的数据范围内正确、高效地运行。2. 核心模板设计与思路拆解一份好的竞赛模板其设计哲学必须服务于“快速、准确、省心”这三个核心目标。下面我将拆解这份数论模板的整体架构和设计背后的考量。2.1 模块化架构从孤立函数到解决方案传统的模板往往是函数的简单罗列例如“gcd函数”、“快速幂函数”。但在实战中问题往往是复合的。比如一道题可能同时涉及质因数分解、欧拉函数和同余方程。因此本模板采用“模块化”和“解决方案”导向的设计。2.1.1 基础工具模块这是所有数论运算的基石追求极致的正确性和效率。精度与类型统一使用long long类型并在任何可能发生乘法溢出的地方如快速幂、组合数计算使用(a * b) % MOD的写法或直接封装防溢出的快速乘。这是国赛数据规模的必然要求。函数设计函数接口清晰职责单一。例如gcd(a, b)只返回最大公约数lcm(a, b)会利用gcd进行计算避免重复逻辑。2.1.2 素数处理模块这是一个典型的需要根据数据规模进行策略选择的领域。试除法适用于单个数n的质数判定或质因数分解时间复杂度 O(√n)。模板中会强调循环条件写成i n / i而非i * i n防止i*i溢出。埃拉托斯特尼筛法埃氏筛适用于需要预处理出[2, N]内所有素数或判断多个数是否为素数的场景复杂度约为 O(N log log N)。模板会提供两种常见优化一是从i*i开始标记二是只筛奇数。欧拉筛线性筛这是国赛模板的必备重点。当 N 达到 10^6 甚至 10^7 时欧拉筛 O(N) 的复杂度优势明显。更重要的是它可以同步求出每个数的最小质因子这为后续的质因数分解和欧拉函数计算提供了 O(log n) 的快速路径。模板会详细注释其“每个合数只被其最小质因子筛掉”的核心逻辑。2.1.3 同余与模运算模块这是数论题的核心也是容易出错的重灾区。快速幂必须支持模运算。模板会提供递归和迭代两种写法并强调迭代写法更常用且不易爆栈。乘法逆元这是重点中的重点。模板会系统性地提供四种求法并明确其适用场景费马小定理仅当模数MOD为质数时inv(a) pow(a, MOD-2, MOD)。扩展欧几里得算法通用解法求解a*x MOD*y 1的整数解x即为逆元。线性递推求 1~n 的逆元当需要连续获取一段数的逆元时这是 O(n) 的预处理神器。公式inv[i] MOD - MOD / i * inv[MOD % i] % MOD;需要推导和记忆。阶乘逆元预处理用于组合数计算。先预处理出阶乘数组fac[i]再求出fac[n]的逆元inv_fac[n]然后倒推inv_fac[i-1] inv_fac[i] * i % MOD。这是竞赛中的标准操作。2.1.4 方程与定理模块将算法封装为直接可用的解决方案。扩展欧几里得不仅用于求逆元更用于求解二元一次不定方程a*x b*y gcd(a, b)。模板会返回gcd以及一组特解(x0, y0)并给出如何推导出通解公式。中国剩余定理解决模数两两互质的同余方程组。模板会提供标准流程和每一步的数学依据。欧拉函数提供单点计算phi(n)和利用欧拉筛线性预处理[1, N]内所有欧拉函数值两种方法。2.2 代码风格与工程化考量为了在赛场上实现“即插即用”模板代码必须极其规范。命名清晰is_prime,get_primes_euler,quick_pow,inv_linear函数名即功能描述。注释精准注释不解释“代码在做什么”因为代码本身应清晰而是解释“为什么这么做”和“关键约束”。例如在欧拉筛旁注释“if (i % primes[j] 0) break;是保证每个合数只被最小质因子筛掉的关键。”边界处理函数开头对特殊输入如n1进行处理返回约定俗成的值如phi[1]1。常用代码块将“读入n预处理欧拉筛和欧拉函数”这样的高频操作封装成清晰的代码块减少现场组装时间。注意模板不是死记硬背的咒语。在整理和使用的过程中理解每个算法背后的数学原理和模板代码的每一个细节才能在遇到变种题目时灵活调整。否则生搬硬套只会适得其反。3. 核心算法模板详解与实战要点本节将深入几个最关键、最容易在赛场上卡住的模板不仅给出代码更剖析其原理和实现细节。3.1 欧拉筛线性筛的透彻理解与实现欧拉筛是素数筛法的终极武器其价值远超“筛出素数”。3.1.1 标准模板代码const int MAXN 1e7 5; // 根据题目数据范围调整 int primes[MAXN], cnt; // primes[]存储所有素数cnt是素数个数 bool st[MAXN]; // st[x]存储x是否被筛掉非素数 int min_prime[MAXN]; // 可选记录每个数的最小质因子 void get_primes_euler(int n) { for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; min_prime[i] i; // 质数的最小质因子是它本身 } // 关键步骤用当前已知的素数 primes[j] 去筛合数 for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; min_prime[primes[j] * i] primes[j]; // 记录最小质因子 if (i % primes[j] 0) break; // 核心保证每个合数只被筛一次 } } }3.1.2 核心原理与“为什么”if (!st[i]) primes[cnt] i;如果i未被标记则它一定是素数。因为它不可能被小于它的数整除那些数之前已经用来筛过了。内层循环for (int j 0; primes[j] n / i; j)用当前数i无论i是素数还是合数乘以已知的素数primes[j]来标记合数primes[j] * i。条件primes[j] n / i是为了防止primes[j] * i超过n导致数组越界这是比primes[j] * i n更安全的写法。灵魂语句if (i % primes[j] 0) break;这是保证线性的关键。当i能被primes[j]整除时说明primes[j]是i的最小质因子因为我们是按顺序遍历素数表的。那么对于下一个素数primes[j1]要标记的合数primes[j1] * i的最小质因子应该是primes[j]因为primes[j1] primes[j]而i里已经包含primes[j]。根据算法设计每个合数只被其最小质因子筛掉这个操作不应该由primes[j1] * i来完成所以必须break。反之如果i % primes[j] ! 0说明primes[j]比i的所有质因子都小那么primes[j]就是primes[j] * i的最小质因子可以放心标记。3.1.3 实战要点与扩展数组大小primes数组大小可以估算素数个数约为n / log(n)。对于n1e7开1e65足够。内存与速度权衡bool st[MAXN]在C中通常只占1字节/元素内存消耗小。如果空间极度紧张如n1e8可以考虑使用bitset。核心价值——最小质因子记录min_prime数组是欧拉筛的“神级”扩展。有了它我们可以以 O(log n) 的时间对任何一个数x进行质因数分解// 对x进行质因数分解结果存入vectorpairint, int fac中 (质因子指数) vectorpairint, int factorize(int x) { vectorpairint, int fac; while (x 1) { int p min_prime[x], cnt 0; while (x % p 0) { x / p; cnt; } fac.emplace_back(p, cnt); } return fac; }这在解决涉及质因数分解的题目时效率远高于传统的试除法。3.2 逆元全家桶四种求法与应用场景模意义下的除法需要转化为乘以其逆元。掌握所有求逆元的方法是数论模板完备性的体现。3.2.1 费马小定理求逆元条件模数MOD为质数且a不是MOD的倍数。原理a^(MOD-1) ≡ 1 (mod MOD)a * a^(MOD-2) ≡ 1 (mod MOD)。所以a^(MOD-2)就是a的逆元。模板// 快速幂模板 ll qpow(ll a, ll b, ll mod) { ll res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } ll inv_fermat(ll a, ll mod) { return qpow(a, mod - 2, mod); }3.2.2 扩展欧几里得求逆元条件a与MOD互质gcd(a, MOD) 1。原理求解方程a*x MOD*y 1的整数解xx在模MOD下的值就是a的逆元。模板// 扩展欧几里得返回gcd(a,b)并修改x,y为方程 a*xb*ygcd(a,b) 的一组特解 ll exgcd(ll a, ll b, ll x, ll y) { if (!b) { x 1, y 0; return a; } ll d exgcd(b, a % b, y, x); y - a / b * x; return d; } ll inv_exgcd(ll a, ll mod) { ll x, y; ll d exgcd(a, mod, x, y); // 确保gcd(a, mod)1 return (x % mod mod) % mod; // 调整到[0, mod)范围内 }3.2.3 线性递推求 1~n 的逆元条件模数MOD为质数通常需要求1到n所有数模MOD的逆元。原理与推导设MOD k * i r(其中0 r i)。则有k * i r ≡ 0 (mod MOD)。两边同时乘以inv(i) * inv(r)得到k * inv(r) inv(i) ≡ 0 (mod MOD)。所以inv(i) ≡ -k * inv(r) (mod MOD)。由于k MOD / ir MOD % i所以公式为inv[i] MOD - MOD / i * inv[MOD % i] % MOD。模板const int MAXN 1e6 5; const ll MOD 1e9 7; ll inv[MAXN]; void init_inv(int n) { inv[1] 1; for (int i 2; i n; i) { inv[i] MOD - MOD / i * inv[MOD % i] % MOD; } }3.2.4 阶乘逆元预处理用于组合数场景频繁计算组合数C(n, m) n! / (m! * (n-m)!)模MOD为质数。步骤预处理阶乘数组fac[i] i! % MOD。用费马小定理或线性递推求出fac[n]的逆元inv_fac[n]。利用关系inv_fac[i] inv_fac[i1] * (i1) % MOD倒推出所有inv_fac[i]。模板ll fac[MAXN], inv_fac[MAXN]; void init_comb(int n) { fac[0] 1; for (int i 1; i n; i) fac[i] fac[i-1] * i % MOD; // 方法1用费马小定理求 fac[n] 的逆元再倒推 inv_fac[n] qpow(fac[n], MOD-2, MOD); for (int i n-1; i 0; i--) { inv_fac[i] inv_fac[i1] * (i1) % MOD; } // 方法2如果用线性递推求逆元也可以先 init_inv(n)然后 inv_fac[i] inv[fac[i]]但不如倒推高效。 } ll C(int n, int m) { if (m 0 || m n) return 0; return fac[n] * inv_fac[m] % MOD * inv_fac[n - m] % MOD; }实操心得在蓝桥杯国赛环境中MOD经常是1e97这样的质数。对于组合数问题阶乘逆元预处理是标准操作务必熟练。线性递推求逆元则在需要用到连续数字逆元如多项式运算时非常有用。扩展欧几里得是通用保底方案。费马小定理最简单但要注意前提条件。3.3 扩展欧几里得算法与中国剩余定理3.3.1 扩展欧几里得求解不定方程与逆元前面已经给出了exgcd的模板。这里重点讲其应用。求解a*x b*y c先用exgcd(a, b, x0, y0)求出a*x0 b*y0 gcd(a, b)的特解。如果c % gcd(a, b) ! 0则无整数解。否则令k c / gcd(a, b)原方程的一组特解为x1 x0 * k,y1 y0 * k。通解为x x1 (b/d)*t,y y1 - (a/d)*t其中d gcd(a, b)t为任意整数。求逆元如前所述是c1的特殊情况。3.3.2 中国剩余定理同余方程组求解问题求解方程组x ≡ a_i (mod m_i)其中m_i两两互质。原理令M m1 * m2 * ... * mkM_i M / m_i。由于m_i互质M_i与m_i也互质可求M_i模m_i的逆元t_i即M_i * t_i ≡ 1 (mod m_i)。则解为x Σ(a_i * M_i * t_i) mod M。模板ll CRT(vectorll a, vectorll m) { ll M 1, x 0; int k a.size(); for (int i 0; i k; i) M * m[i]; for (int i 0; i k; i) { ll Mi M / m[i]; ll ti, y; // 求 Mi 模 m[i] 的逆元 ti exgcd(Mi, m[i], ti, y); // Mi * ti m[i] * y 1 // 调整 ti 到正数 ti (ti % m[i] m[i]) % m[i]; x (x a[i] * Mi % M * ti % M) % M; } return (x % M M) % M; }注意标准CRT要求模数两两互质。对于不互质的情况需要使用扩展中国剩余定理通过合并方程的方式求解其本质是多次使用扩展欧几里得算法。4. 模板的实战应用与组合技巧有了独立的模板模块如何在复杂问题中组合使用它们是区分高手与新手的另一关键。4.1 典型问题拆解一道综合数论题假设题目描述求Σ_{i1}^{n} Σ_{j1}^{m} gcd(i, j)其中n, m ≤ 1e7。结果对1e97取模。4.1.1 思路分析直接枚举i, j是 O(n*m) 不可行。常见思路是莫比乌斯反演或利用欧拉函数。这里展示一个利用欧拉函数的经典结论Σ_{i1}^{n} Σ_{j1}^{m} gcd(i, j) Σ_{d1}^{min(n,m)} φ(d) * floor(n/d) * floor(m/d)。 其中φ(d)是欧拉函数。理解这个结论需要一定的数论基础但我们可以将其作为已知结论来应用。4.1.2 模板组合应用预处理由于n, m高达1e7我们需要用欧拉筛线性预处理出[1, min(n,m)]范围内所有数的欧拉函数值phi[i]。计算答案预处理后答案就是Σ_{d1}^{min(n,m)} phi[d] * (n/d) * (m/d)。这里(n/d)和(m/d)是整除在计算时要注意使用long long防止中间结果溢出。优化直接求和是 O(min(n,m))对于1e7可能刚好卡过。但可以进一步用数论分块优化到 O(√min(n,m))这是更高级的技巧。但即使不优化线性预处理加线性求和在1e7量级、时限较宽松的比赛中也可能通过。4.1.3 核心代码框架#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 1e7 5; const ll MOD 1e9 7; int primes[MAXN], cnt; bool st[MAXN]; int phi[MAXN]; // 欧拉函数值 ll sum_phi[MAXN]; // 欧拉函数前缀和 void init_euler(int n) { phi[1] 1; for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; phi[i] i - 1; // 质数的欧拉函数值为 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]; // 情况1 break; } else { phi[primes[j] * i] phi[i] * (primes[j] - 1); // 情况2 } } } // 计算前缀和方便后续求和如果使用数论分块 for (int i 1; i n; i) { sum_phi[i] (sum_phi[i-1] phi[i]) % MOD; } } int main() { int n, m; cin n m; int up min(n, m); init_euler(up); ll ans 0; // 方法1直接求和 O(up) for (int d 1; d up; d) { ans (ans (ll)phi[d] * (n / d) % MOD * (m / d) % MOD) % MOD; } cout ans endl; // 方法2数论分块优化 O(sqrt(up)) 进阶 // ans 0; // for (int l 1, r; l up; l r 1) { // r min(n / (n / l), m / (m / l)); // ans (ans (sum_phi[r] - sum_phi[l-1] MOD) % MOD * (n / l) % MOD * (m / l) % MOD) % MOD; // } // cout ans endl; return 0; }这个例子完美展示了如何将欧拉筛模板升级为欧拉函数线性筛模板并将其应用于一个具体问题。模板的价值在于当你知道这个结论后实现部分变得机械而可靠。4.2 组合数计算的高阶应用组合数计算是数论中的常客。除了基本的C(n, m)还有更多变体。4.2.1 预处理组合数模板上述init_comb和C函数是基础。注意fac和inv_fac数组的大小要开到需要的最大n。4.2.2 卢卡斯定理当模数MOD比较小甚至不是质数但通常是质数且n, m非常大时需要使用卢卡斯定理。原理C(n, m) % p C(n%p, m%p) * C(n/p, m/p) % p其中p是质数。模板ll lucas(ll n, ll m, ll p) { if (m 0) return 1; // 小范围直接计算这里需要有小范围的组合数计算函数C_small return C_small(n % p, m % p, p) * lucas(n / p, m / p, p) % p; } // C_small 可以用预处理的阶乘逆元来算但p较小也可以直接算。 ll C_small(ll n, ll m, ll p) { if (m n) return 0; ll a 1, b 1; for (int i 1; i m; i) { a a * (n - i 1) % p; b b * i % p; } return a * qpow(b, p-2, p) % p; // 费马小定理求逆元 }在蓝桥杯国赛中如果出现n, m巨大如1e18但模数p较小如1e5的组合数问题卢卡斯定理是唯一选择。5. 赛场策略、调试与常见“坑点”即使模板准备得再充分赛场上的临场发挥也至关重要。5.1 模板使用策略赛前准备将整理好的模板打印出来或者放在IDE一个固定的、触手可及的位置。按模块素数、同余、组合数、方程做好标签方便快速查找。阅读题目时联想看到“质数”、“因子”、“最大公约数”、“同余方程”、“方案数组合数”、“模运算”等关键词立刻在脑海中映射到对应的模板模块。复制后先适配复制模板代码后第一件事是修改变量名、数组大小MAXN、模数MOD等全局参数使其符合当前题目要求。避免因忘记修改导致数组越界或答案错误。先写暴力验证对于复杂的数论推导如果时间允许可以先写一个小的暴力程序例如n, m 100用于验证模板算法在小数据上的正确性。这能极大增强信心并帮助发现逻辑错误。5.2 常见“坑点”与调试技巧5.2.1 数据范围与溢出这是数论题最经典的错误来源。int溢出即使最终答案在int范围内中间计算也可能溢出。无脑使用long long是竞赛中的好习惯。乘法溢出(a * b) % MOD中a*b可能溢出long long当a, b, MOD都在1e9量级时。解决方案使用__int128如果编译器支持。使用快速乘算法将乘法转化为加法类似快速幂。ll qmul(ll a, ll b, ll mod) { ll res 0; while (b) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; } // 然后在快速幂中用 qmul 替代乘法数组越界欧拉筛的primes数组大小要足够。估算公式π(n) ≈ n / ln(n)。对于n1e7开1e6足够。5.2.2 模运算的陷阱负数取模C中%运算结果符号与被除数相同。(x % MOD MOD) % MOD是得到[0, MOD)范围内标准非负余数的标准写法。除法与逆元牢记(a / b) % MOD ! (a % MOD) / (b % MOD)。必须将除法转换为乘b的逆元。逆元不存在当a与MOD不互质时a模MOD的逆元不存在。在使用费马小定理要求MOD是质数且a非MOD倍数或exgcd要求gcd(a, MOD)1前要确认条件。5.2.3 算法细节错误欧拉筛的break条件if (i % primes[j] 0) break;这一行写错筛法就退化为埃氏筛甚至出错。扩展欧几里得的递归与参数exgcd(b, a % b, y, x);和y - a / b * x;这两行需要准确记忆。可以自己推导一下理解其原理。组合数边界C(n, m)中要判断m0 || mn的情况返回0。5.2.4 调试方法小数据测试用n10, 20这样的小数据对比暴力算法和模板算法的结果。中间输出在复杂算法中输出关键中间变量如筛出的素数列表、计算的欧拉函数值、逆元数组的前几项等与手算结果对比。静态查错写完代码后花一分钟静心阅读检查数组大小、变量类型、循环边界、条件判断和公式翻译是否正确。5.3 心理建设与时间管理数论题往往代码短但思维难度高。在国赛环境下不要死磕如果30分钟内没有清晰的思路果断标记后跳过去做其他有把握的题目。比赛是总分最大化不是单题得分。善用暴力找规律对于公式推导题如果数学上暂时推不出来可以尝试写暴力程序枚举小数据观察输入输出规律有时能直接发现公式或者为推导提供线索。检查再提交数论题一旦WA调试起来可能比长代码的题更耗时。提交前务必用几个边缘用例如n0,1,MOD边界测试一下。这份“第十二届国赛蓝桥杯个人模板_数论篇”的终极目标是让你在赛场上面对数论问题时能省下“重复造轮子”和“调试基础代码”的时间将全部精力投入到更高层次的算法思维和问题建模上。它就像一位可靠的战友负责处理好所有底层、琐碎但至关重要的细节让你能更专注于战斗本身。最后记住模板是死的人是活的。深刻理解每一个算法并在大量的练习中内化这些模板你才能真正做到“手中无板心中有板”在关键时刻游刃有余。