从莫比乌斯反演到Min_25筛：算法竞赛中的数论求和与性能优化实战

1. 项目概述一场算法竞赛中的硬核挑战看到这个标题很多参加过算法竞赛的朋友可能会心一笑或者倒吸一口凉气。“国赛模拟”、“求和”、“莫比乌斯反演”、“Min_25筛”最后还加上一个“卡常”这几个关键词组合在一起几乎就是一道典型的高难度数论压轴题的“身份证”。这不仅仅是一道题更像是一个完整的项目它考察的是选手从数学理论推导、算法设计实现到极致性能优化也就是“卡常”的全链路能力。简单来说这道题会给你一个关于正整数n的求和表达式这个表达式通常与数论函数比如欧拉函数、莫比乌斯函数、除数函数等的卷积有关最终要求你计算当n非常大比如1e10甚至更大时这个和式的值。直接暴力计算是天文数字级别的复杂度必须依靠深刻的数学变换和高效的筛法算法才能解决而“卡常”则是为了在严格的时间限制内让这些本就复杂的算法能够跑得更快一点。这道题的价值在哪里对于竞赛选手而言它是冲击顶级奖项必须翻越的高山掌握它意味着对数论和算法优化有了深刻理解。对于普通的算法爱好者或开发者虽然工作中可能永远不会需要手写一个 Min_25 筛但解决这类问题的过程中所锻炼的问题转化能力、对复杂度的敏感度以及为了优化性能而深入底层细节的执着是任何领域处理大规模计算问题时都非常宝贵的思维模式。接下来我就以一个过来人的视角拆解一下这道题背后的核心逻辑、实现细节以及那些让人又爱又恨的“卡常”技巧。2. 核心思路拆解从暴力到优雅的数学魔法面对一个巨大的求和问题我们的思考路径应该是阶梯式的先理解它是什么再寻找数学工具简化它最后用算法高效计算它。2.1 问题原型与暴力法的死胡同题目中的“求和”通常形如S(n) ∑_{i1}^{n} f(i)或者更复杂的二重求和例如S(n) ∑_{i1}^{n} ∑_{j1}^{n} [gcd(i, j) k] * g(i) * h(j)其中f,g,h是某种数论函数[ ]是艾弗森括号条件成立为1否则为0。当n很小比如n 1e6时我们可以用欧拉筛线性预处理出需要的数论函数值然后直接循环累加。时间复杂度O(n)或O(n log n)尚可接受。但国赛级别的题目n动辄1e10O(n)的循环连一步都走不完假设每秒1e8次运算需要100秒而竞赛通常限制1秒。暴力法在此完全失效。2.2 第一重魔法莫比乌斯反演当求和式中出现gcd(i, j) k这类条件时莫比乌斯反演几乎是标准起手式。它的核心思想是将“等于”条件转化为“整除”条件的求和利用莫比乌斯函数μ(d)的容斥原理性质。经典套路示例 计算∑_{i1}^{n} ∑_{j1}^{m} [gcd(i, j) 1]。利用公式[n 1] ∑_{d|n} μ(d)。将n替换为gcd(i, j)得到[gcd(i, j) 1] ∑_{d|gcd(i, j)} μ(d)。交换求和顺序将d的求和提到外面。因为d | gcd(i, j)等价于d | i且d | j。原式转化为∑_{d1}^{min(n,m)} μ(d) * ⌊n/d⌋ * ⌊m/d⌋。这样一来我们从需要枚举所有i, j对O(nm)转化为了只需要枚举dO(min(n, m))。并且⌊n/d⌋和⌊m/d⌋的值在d变化时是分段的可以运用数论分块技巧将复杂度进一步降至O(√min(n, m))。这是第一次飞跃。实操心得莫比乌斯反演的关键在于熟练记忆几个常用公式和变换套路。在竞赛中时间紧迫往往需要直接套用变形后的结果。建议准备一个“数论工具箱”把像∑_{d|n} μ(d) [n1]∑_{d|n} φ(d) n这些恒等式以及它们的推广形式都提前推导好并记牢。2.3 第二重魔法Min_25 筛莫比乌斯反演结合数论分块后我们得到了一个形如∑_{d1}^{n} μ(d) * F(⌊n/d⌋)的式子。这里F(x)是一个关于⌊n/d⌋的、计算起来很快的函数比如多项式函数。问题似乎变成了O(√n)个F(x)的计算。但是F(x)的计算常常又需要用到前缀和例如G(n) ∑_{i1}^{n} μ(i)或∑_{i1}^{n} φ(i)。当n很大时1e10我们无法用线性筛预处理出1~n所有μ(i)或φ(i)的值。这时就需要Min_25 筛这样的亚线性筛法。它的目标正是快速计算某些积性函数f(i)在i从1到n的前缀和时间复杂度约为O(n^{3/4} / log n)或优化后O(n^{2/3})空间复杂度O(√n)。Min_25筛的核心思想分两步第一步构造完全积性函数找到一个完全积性函数f(i)使得在质数p处f(p) f(p)。这一步的目的是为了用一个简单的函数来拟合原函数在质数处的值从而可以用埃氏筛的思路来筛选。第二步递归引入最小质因子利用动态规划的思想从大到小考虑每个数的最小质因子通过递归或递推的方式从“只有质数”的情况逐步加回合数的贡献。这个过程通常用一个函数S(n, j)来表示其中j表示当前考虑的最小质因子不小于第j个质数p_j。这个过程非常精妙但实现起来细节极多尤其是边界处理和数组下标映射。它要求函数f(p^k)在质数幂处的值能够快速计算。注意事项Min_25筛的模板性很强但绝非“黑盒”。你必须彻底理解其状态定义g[n][j]和S(n, j)的含义以及它们如何从“质数近似”过渡到“真实函数值”。自己动手推导一遍f(p)p^k这种简单函数的计算过程是掌握它的不二法门。直接套用网上代码而不知其所以然稍作改动就会出错。3. 算法实现与细节剖析理论懂了代码才是试金石。这里我们以计算S(n) ∑_{i1}^{n} φ(i)欧拉函数前缀和为例串联起莫比乌斯反演如果需要和 Min_25 筛。3.1 莫比乌斯反演部分实现假设我们最终问题化简后需要计算∑_{d1}^{n} μ(d) * floor(n/d)^2。我们需要快速得到μ(d)的前缀和M(n) ∑_{i1}^{n} μ(i)。// 数论分块计算 ∑ μ(d) * F(n/d) long long solve_mobius(long long n) { long long ans 0; for (long long l 1, r; l n; l r 1) { r n / (n / l); // 找到当前块的范围 [l, r]其中 floor(n/i) 值相同 long long block_sum M(r) - M(l-1); // 计算 μ(d) 在这一块的前缀和之差 long long f_val F(n / l); // 计算 F(floor(n/l))这里 F(x) x*x ans block_sum * f_val; } return ans; }这里的关键是M(x)函数它需要高效计算μ(i)的前缀和。当x很大时就需要下面的 Min_25 筛。3.2 Min_25筛计算 μ(n) 前缀和Min_25筛的第一步是处理质数。对于μ(n)在质数p处μ(p) -1。我们选择一个完全积性函数f(i) -1常数函数-1来拟合。因为对于任何正整数if(i) -1都是完全积性的且在质数p处值相等。步骤一预处理质数并计算 g(n, j)g(n, j)表示在区间[2, n]中所有质数或者最小质因子大于p_j的数的f函数值之和。初始时g(n, 0)表示所有数的f值之和可以公式计算。然后我们依次用质数p_j去筛。// 预处理部分关键代码 (概念性) vectorlong long w; // 存储所有需要处理的 n/i 的下取整值 vectorint idx1, idx2; // 映射将大的 n/i 映射到数组下标 vectorlong long g0; // 存储 g(n, j) 的结果这里 f(i)-1所以 g 存储的是“负数个数” // 初始化 g0[n] - (n - 1) 因为1不算从2到n每个数贡献-1 for (auto x : w) { g0[i] -(x - 1); } // 用质数筛 for (int j 1; j pcnt; j) { long long p primes[j]; long long p_sq p * p; for (int i 1; i w.size() w[i] p_sq; i) { long long n_div_p w[i] / p; int k (n_div_p sqrt_n ? idx1[n_div_p] : idx2[n / n_div_p]); g0[i] g0[i] - (g0[k] - (j - 1)); // 状态转移减去最小质因子恰好为 p_j 的那些数的贡献 // 公式为g(n, j) g(n, j-1) - f(p_j) * ( g(n/p_j, j-1) - sum_{i1}^{j-1} f(p_i) ) // 这里 f(p_j) -1 sum_{i1}^{j-1} f(p_i) -(j-1) } }步骤二递归计算 S(n, j)S(n, j)表示在区间[2, n]中所有最小质因子大于等于p_j的数的真实函数f(i)值之和。对于μ(n)f(1) 1但通常不包含1。f(p) -1。f(p^k) 0当k 2因为含有平方因子。long long S(long long x, int j) { if (x 1 || primes[j] x) return 0; // 获取 x 在数组中的下标 int k (x sqrt_n ? idx1[x] : idx2[n / x]); // 起始答案所有质数的贡献 (g0[k] - (j-1))注意这里 g0 存的是 f 值对于质数 ff-1 // 所以质数贡献就是 (g0[k] - (j-1))。但 g0[k] 是负数-(j-1)也是负数注意符号。 // 更标准的写法是res - (g0[k] - (-(j-1))) (j-1) - g0[k]? 这里容易错 // 正确的理解g0[k] 现在等于 g(x, j)即用前j个质数筛完后剩下的“负数个数”。 // 我们要求的是 sum_{p p_j, p是质数} f(p) sum_{p p_j} (-1) - (质数个数)。 // 而“质数个数” (j-1) (g(x, j) 的绝对值?) 不对。 // 实际上在Min_25筛的最终推导中质数部分的贡献是 (g(x, j) - (j-1)) * f(p)在质数处的公共值? 这里需要根据模板调整。 // 鉴于其复杂性下面给出一个更清晰的伪代码思路 long long res - (g0[k] - (j - 1)); // 假设我们的g0存储的是“负数个数”那么-(负数个数)就是正数个数逻辑要理顺。 // 更常见的模板写法计算f(p)p的k次方时 // res (g1[k] - sp1[j-1]) * 1; // 这里1是f(p)p^k的系数。 // 对于 μ f(p) -1 所以 sp1[j-1] - (j-1) // g1[k] 存储的是 ∑ f(i) ∑ (-1) - (符合条件的数的个数) // 所以 res (g1[k] - sp1[j-1]) * (-1) (-cnt (j-1)) * (-1) cnt - (j-1) // 其中 cnt 是 [2, x] 中最小质因子 p_j 的数的个数用f-1拟合。 // 可以看到直接推导极易混乱。强烈建议在理解原理后使用一个经过验证的、针对特定函数如f(p)p, f(p)1的模板然后修改其中的函数值计算部分。 // 合数部分贡献 for (int i j; i pcnt primes[i] * primes[i] x; i) { long long p primes[i]; long long pe p; for (int e 1; pe * p x; e) { res S(x / pe, i 1) * f(pe) f(pe * p); // 这里f是真实函数 pe * p; } } return res; } // 最终 μ 的前缀和 M(n) S(n, 1) 1; 加上f(1)1踩坑实录Min_25筛的实现中下标映射idx1,idx2和g数组的初始化是第一个易错点。w数组存储了所有不同的n/i数量级是O(√n)。g数组的初始值g(n, 0)必须根据你选择的完全积性函数f精确计算。对于f(i)1求质数个数g(n,0)n-1。对于f(i)i求质数和g(n,0)n*(n1)/2 - 1。这里千万不能错。3.3 性能瓶颈与“卡常”实战即使使用了O(n^{2/3})的 Min_25 筛当n接近题目上限时运行时间也可能擦边。这时“卡常”优化常数时间就至关重要了。1. 预处理与记忆化质数数组用线性筛预处理√n范围内的质数存于连续数组。记忆化 S(n, j)递归计算S时对于相同的(n, j)可能会重复计算。可以用unordered_map或手写哈希表进行记忆化。但注意n是long longj是质数下标直接映射内存可能爆炸。一个经典优化是只记忆化n较小比如n 1e6或者j固定如j1时n对应的结果。因为递归树中n会快速减小。预处理小范围前缀和对于i N例如N 1e6直接用线性筛预处理出μ(i)或φ(i)的前缀和数组sum_mu[N]。在 Min_25 的S(n, j)函数中如果n N直接返回sum_mu[n] - sum_mu[primes[j-1]]如果j1。这能截断大量递归。2. 循环与递归优化递归转迭代Min_25 筛的S函数本质是递归但我们可以用栈模拟或者用递推的 DP 方式实现第二维有时能减少函数调用开销。数论分块循环for (long long l 1, r; l n; l r 1)这个循环是标准的。确保r n / (n / l)的计算只做一次且用整数除法。避免重复计算在循环内部n / l的值可能会多次使用用一个变量存起来。3. 数据结构与存取优化使用连续数组而非vector对于g,w,idx等大小确定O(√n)的数组可以使用new或全局静态数组减少vector的动态开销。使用整数运算避免模运算如果答案不需要取模全程使用long long。即使需要取模也只在最后加法乘法时取模中间过程尽量用long long暂存减少模运算次数。优化缓存访问数组时尽量顺序访问提高缓存命中率。例如在筛g数组时内层循环i是顺序的。4. 编译器优化开启O2,O3优化。使用inline标记频繁调用的小函数如获取下标的函数get_idx(long long x)。使用register关键字现代编译器可能自动优化但写上无妨标记循环变量。// 一个“卡常”后的 get_idx 函数示例 inline int get_idx(long long x) { if (x sqrt_n) return idx1[x]; else return idx2[n / x]; }独家技巧在 Min_25 筛计算合数部分时循环for (int e 1; pe * p x; e)中当e1时f(pe)f(p)已经包含在质数部分了这里需要根据模板定义仔细核对。有些模板的S(n,j)定义排除了单个质数的情况那么合数部分就从e2开始。这个边界处理不对会导致结果错误或重复计算。务必用n较小的样例比如n100将你的 Min_25 筛结果与线性筛暴力结果对比逐项调试。4. 典型问题排查与调试策略实现这么复杂的算法不出错几乎是不可能的。下面是一些常见问题和排查手段。问题1结果错误小数据对不上。检查点首先用n 1000的数据对比你的 Min_25 筛和线性筛暴力程序。可能原因g数组初始化公式错误。重新推导f(i)的前缀和公式。S(n, j)递归中质数部分贡献计算错误。这是最复杂的部分建议用f(i)i求质数和这个简单的函数来调试因为它的结果(n*(n1)/2 - 1 - 所有合数和)很容易验证。合数部分递归边界错误。确保primes[i] * primes[i] x这个条件正确并且S(x/pe, i1)中的i1传递正确。莫比乌斯反演公式推导错误。回头检查数学推导用简单数据代入验证。问题2程序超时。检查点用最大的n测试用clock()函数分段计时找出耗时最长的部分。可能原因记忆化没有生效或记忆化策略不好。尝试输出递归调用次数如果次数远大于O(n^{2/3})说明记忆化失效。预处理范围N设置太小导致递归过深。适当增大线性筛预处理的范围比如到1e7用空间换时间。频繁使用map或unordered_map进行记忆化其常数过大。对于n不大的情况可以考虑用vectorlong long数组下标就是n本身如果n是int范围。或者使用两个unordered_map分别存储n较大和较小的结果。数论分块中计算M(r) - M(l-1)时M(x)函数本身调用频繁且没有优化。确保M(x)函数内部对小数据有直接返回查预处理数组对大数据才走 Min_25 筛并且M(x)的结果自身也被记忆化。问题3内存超限。检查点√n大约是1e5到1e6量级你的g,w数组大小应为2 * √n。可能原因错误地开了O(n)大小的数组。确认所有大数组的大小都是O(√n)。记忆化S(n, j)时存储了太多状态。考虑更激进的记忆化策略比如只记忆化j1的状态或者只记忆化n较小的状态。使用了mappairlong long, int, long long这样臃肿的结构。如果必须记忆化可以考虑将(n, j)编码成一个long long键例如(n 20) | j前提是j不会太大然后用一个unordered_maplong long, long long存储。调试策略单元测试将 Min_25 筛封装成一个类单独测试其计算∑μ(i)和∑φ(i)的功能与线性筛结果对比。中间输出在S(n, j)函数中输出关键的(n, j, res)观察递归过程。对于小n可以手算验证。对拍写一个暴力程序n 1e6一个优化程序用脚本随机生成大量的n包括大数和小数比较两者结果是否一致。这是发现隐蔽错误的最有效方法。5. 从竞赛到工程思维模式的延伸解这道题的过程是一次完整的“高性能计算”微型项目演练。它带给我们的远不止一个算法模板。数学建模能力将一个看似复杂的求和问题通过莫比乌斯反演转化为可快速计算的形式这本质上是问题重构的能力。在工作中面对一个性能瓶颈能否跳出代码层面从数据模型、业务流程的数学本质上去寻找优化点分层优化思想我们用了三层优化1) 数学变换莫反降低问题阶数2) 高效算法Min_25筛突破线性限制3) 代码级“卡常”压榨最后一点性能。这对应着系统优化的典型层次架构设计、算法选型、代码实现。每一层都有其极限和收益合理的投入方向至关重要。对复杂度的敬畏O(n)到O(√n)再到O(n^{2/3})每一次复杂度阶的降低都带来了数量级的性能提升。这提醒我们在设计和评审算法时时间复杂度是首要的衡量标准。在数据规模大的场景下一个O(n log n)的算法可能比一堆O(n)但常数小的算法更糟糕。工具与思维的平衡Min_25筛很复杂你可以选择死记硬背模板。但如果你理解了它的核心思想——用完全积性函数逼近、用最小质因子动态规划你就有可能将其思想迁移到其他类似问题甚至对模板进行修改以适应新的函数。这即是“工具”与“内化思维”的区别。最后关于“卡常”我想说在竞赛中它是必要的技能但在实际工程中它通常是最后才考虑的手段。清晰的代码结构、可维护性比那一点点常数优化更重要。除非你是在编写基础库如标准库、数值计算库或者性能确实是核心需求如高频交易、实时渲染。这道题将“卡常”作为一部分更多的是为了锻炼我们在极限环境下对代码性能的掌控力。在实际工作中我们更应该追求在算法和架构层面上的优雅与高效。