1. 从一道“国赛模拟”题说起当求和遇上数论天花板最近在整理一些算法竞赛的经典题目翻到了这道被圈内人称为“数论劝退题”的国赛模拟题。它的核心就一个词求和。但别被这个词骗了这可不是简单的123...n。题目要求计算的是一个定义在正整数上的函数f(n)的前n项和而这个f(n)本身往往又是一个与数论函数比如欧拉函数、除数函数相关的复杂表达式。当n的规模达到10^10甚至更高时任何O(n)的暴力循环都是痴人说梦甚至连O(sqrt(n))的常规数论分块都可能力不从心。这道题几乎是把算法竞赛中数论方向最硬核的两块内容——莫比乌斯反演和Min_25筛——强行焊在了一起最后还贴心地附赠了一个“卡常”的标签堪称“优雅”与“暴力”的终极结合体。我最初看到这个标题时感觉就像有人告诉我“请用微积分和量子力学的方法精确计算一下你从家到公司路上踩死了多少只蚂蚁。” 荒谬但又让人忍不住想去挑战。莫比乌斯反演负责将题目中天书般的求和式转化为我们相对熟悉、可处理的数论函数形式这是“优雅”的理论部分。而 Min_25筛则是处理超大范围1e10量级数论函数前缀和的“暴力”数值工具其原理复杂实现精巧。至于“卡常”则是这道题最后的现实考验即便你理论全对筛法也会写但如果不把时间和空间优化到极致依然会在巨大的数据规模面前超时或超内存。这篇文章我就来拆解这道题背后的完整解题链条。我们不会停留在“套公式”的层面而是深入每一步“为什么这么做”并分享在实现 Min_25筛以及应对“卡常”时那些在标准题解里不会写的、血泪换来的经验。无论你是正在备赛的选手还是对数论算法感兴趣的开发者相信这篇融合了理论推导与工程实践细节的长文都能给你带来收获。2. 破题之钥莫比乌斯反演如何化简求和式面对一个复杂的求和问题直接硬刚往往是死路一条。莫比乌斯反演在这里扮演的角色就像一个高明的“翻译官”把一句晦涩难懂的“古文”原求和式翻译成一句结构清晰、词汇简单的“现代文”反演后的式子。2.1 理解题设中的f(n)与目标通常这类题目的f(n)会与数的因子结构强相关。例如一个非常经典的套路是定义f(n) ∑_{d|n} g(d) * h(n/d)或者与最大公约数、最小公倍数挂钩。我们的最终目标是计算S(n) ∑_{i1}^{n} f(i)。第一步永远不是急着写代码而是拿起纸笔对f(n)进行形式化的推导。假设我们遇到一个典型情况f(n) ∑_{d|n} μ(d) * d其中μ(d)是莫比乌斯函数。这看起来已经很简单了但直接求前缀和S(n) ∑_{i1}^{n} ∑_{d|i} μ(d) * d依然是O(n log n)的复杂度对于n1e10不可行。这时我们需要运用莫比乌斯反演最核心的技巧交换求和顺序。这是将双重求和简化的关键。S(n) ∑_{i1}^{n} ∑_{d|i} μ(d) * d ∑_{d1}^{n} μ(d) * d * ∑_{i1}^{n} [d|i] // [d|i] 在 d整除i时为1否则为0 ∑_{d1}^{n} μ(d) * d * floor(n/d)看通过交换求和顺序我们把一个需要对每个i枚举其因子的问题转化为了对每个因子d计算其贡献的问题。式子变成了∑ μ(d) * d * floor(n/d)。这已经是一个可以用数论分块整除分块优化的标准形式了因为floor(n/d)的值是成段不变的。复杂度可以优化到O(sqrt(n))。注意这是最理想的情况。实际题目中的f(n)可能更复杂反演后得到的函数可能不是μ(d)*d这么简单而是一个需要单独计算前缀和的函数比如∑ μ(d)*σ(d)σ是约数和函数。这时O(sqrt(n))的数论分块依然需要那个函数的前缀和而该函数前缀和的计算本身就可能需要用到 Min_25筛。这就是两者产生联系的地方。2.2 反演后的常见结构分析与应对策略经过反演我们通常得到形如S(n) ∑_{g(d)} * floor(n/d)的式子其中g(d)是一个积性函数或者可以拆分成积性函数的组合。此时计算S(n)的瓶颈就转移到了如何快速计算g(d)的前缀和G(n) ∑_{i1}^{n} g(i)上。根据g(d)的性质和n的大小我们有几种策略线性筛预处理如果n 1e7我们可以用欧拉筛线性筛在O(n)时间内预处理出所有g(i)的值及其前缀和。这是最快最直接的方法。杜教筛如果g(d)能找到另一个合适的积性函数h使得g与h的狄利克雷卷积(g*h)的前缀和很容易计算那么可以使用杜教筛在O(n^{2/3})的时间复杂度内计算出G(n)。这对于n 1e10通常是可行的。Min_25筛当g(d)不是经典的可杜教筛函数或者题目为了“卡”你而故意将n设置得极大如1e11,1e12或者g(d)在素数幂处的表达式比较复杂时杜教筛可能失效或难以构造。这时Min_25筛就成为了最后的“重型武器”。它能够以大约O(n^{3/4} / log n)的复杂度计算一大类积性函数的前缀和。在这道“国赛模拟”题中出题人将n设置到1e10量级并且设计的g(d)函数往往刻意避开了简单的杜教筛构造因此Min_25筛成为了必须掌握的解题环节。这也正是标题中点出“Min_25筛”的原因——它不是可选项而是通关的必选项。3. Min_25筛核心原理拆解不是“黑盒”而是“施工图”很多人把 Min_25筛当作一个板子来背这其实非常危险。一旦题目稍有变化或者需要优化背板子的人就会束手无策。我们必须理解其背后的“施工图”。Min_25筛的核心思想是分类统计把所有数按最小质因子来分类处理。它通过两步来求解积性函数f(x)的前缀和S(n)。3.1 第一步计算质数处的贡献SP我们定义g(n, j)表示在2~n的所有整数中满足“是质数”或者“最小质因子大于第j个质数P_j”的数的f函数值之和。这里f被替换成了一个完全积性函数f这个f需要在所有质数p处的值与原积性函数f(p)相等。为什么要引入这个f因为完全积性函数f(ab) f(a)f(b)的性质使得我们可以用类似埃氏筛的方法进行递推。初始时g(n, 0)就是所有数包括合数的f值之和这通常可以用一个多项式等价的公式快速计算例如求质数和时f(x)x那么g(n,0) ∑_{i2}^{n} i可以用等差数列求和公式O(1)算得。然后我们从j1开始用第j个质数P_j去“筛”掉那些最小质因子恰好是P_j的数。递推公式为g(n, j) g(n, j-1) - f(P_j) * [ g(floor(n/P_j), j-1) - g(P_j-1, j-1) ]这个公式怎么理解g(n, j-1)是还没用P_j筛之前的结果。我们要减去的是那些最小质因子等于P_j的数。这些数可以写成P_j * t其中t的最小质因子 P_j否则P_j就不是最小质因子了并且t P_j。g(floor(n/P_j), j-1)代表了所有满足“是质数或最小质因子 P_j”的t的f值之和。但这里包含了t是质数且 P_j的情况此时P_j * t的最小质因子是t不是P_j所以我们需要减去这部分即g(P_j-1, j-1)。因为f是完全积性的所以f(P_j * t) f(P_j) * f(t)。通过这个递推当P_j^2 n时g(n, j)就不再变化此时g(n, j)的值就是所有n的质数的f(p)之和也就是我们需要的质数处原函数f(p)的和记为SP(n)。实操心得1g(n, j)中的n在实际计算中只会取到floor(n / i)这种形式不同的i只有O(sqrt(n))个。我们需要预处理出这O(sqrt(n))个“关键点”的g值。通常用两个数组ind1(对应i sqrt(n)) 和ind2(对应n/i sqrt(n)) 来映射这些关键点这是实现高效存储和查询的基础也是容易出错的地方。3.2 第二步计算所有数的贡献S有了质数部分的贡献我们还需要加上合数部分的贡献。我们定义S(n, j)表示在2~n的所有整数中最小质因子大于等于P_j的数的f函数值之和。显然最终答案Ans S(n, 1) f(1)通常f(1)1或根据题目定义。S(n, j)可以通过递归计算S(n, j) SP(n) - sum_{i1}^{j-1} f(P_i) sum_{kj} sum_{e1, P_k^{e1} n} [ f(P_k^e) * S(floor(n / P_k^e), k1) f(P_k^{e1}) ]这个公式分两部分质数部分SP(n) - sum_{i1}^{j-1} f(P_i)。这就是所有大于等于P_j的质数的贡献。合数部分枚举最小质因子P_k(kj)再枚举这个质因子的指数e。合数可以表示为P_k^e * t其中t的最小质因子 P_k。因此贡献是f(P_k^e) * S(floor(n / P_k^e), k1)。另外P_k^{e1}本身也是一个合数且最小质因子就是P_k但它对应的t1而S(..., k1)中不包含1所以需要单独加上f(P_k^{e1})。递归的边界条件是当n P_j时S(n, j) 0。实操心得2这个递归看似复杂但有效状态数并不多。可以用记忆化搜索来实现。递归的深度不会太深因为P_k^{e1} n这个条件限制了枚举范围。一个至关重要的剪枝是当P_k * P_k n时合数部分不可能再有贡献因为最小的合数至少是P_k^2此时S(n, j)就等于质数部分的贡献。这个剪枝能极大提升效率。4. 从理论到实践实现Min_25筛的工程细节与“卡常”实战理解了原理实现起来依然处处是坑。“卡常”不仅仅是简单的快读快写更是对算法每个环节的极致压榨。4.1 存储优化与离散化这是Min_25筛实现的第一道坎。我们注意到所有计算中出现的n都是floor(n / i)的形式。这样的值大约有2 * sqrt(n)个。我们预处理一个数组val[1...m]来存储所有这些不同的floor(n/i)。同时我们需要建立从xx是某个floor(n/i)到数组下标的映射。通常这样实现// 假设 n 1e10 ll n, sqrt_n; int m 0; for (ll l 1, r; l n; l r 1) { r n / (n / l); val[m] n / l; // 存储值 if (val[m] sqrt_n) ind1[val[m]] m; // 小值直接映射 else ind2[n / val[m]] m; // 大值通过 n/val[m] 映射 }在g(n, j)的递推中我们访问的是g(floor(n/P_j), j-1)我们需要通过floor(n/P_j)这个值快速找到它在val数组中的下标从而获取对应的g值。ind1和ind2就是用来做这个O(1)查询的。4.2 递推g数组的细节与滚动数组g(n, j)是一个二维状态直接开数组g[m][j]内存会爆炸。观察递推式g(n, j)只依赖于g(..., j-1)。因此我们可以用滚动数组只保留当前j和上一轮j-1的结果。通常我们定义两个数组g1和g2如果f(p)需要多个多项式拟合可能需要更多分别对应当前轮和上一轮。在每一轮用质数P_j筛的时候我们从大到小遍历val中的n即val[i]。因为递推公式中g(n, j)依赖于g(floor(n/P_j), j-1)而floor(n/P_j)一定小于等于n。从大到小遍历可以保证在计算g(val[i], j)时所需要的g(floor(val[i]/P_j), j-1)已经被更新为当前轮 (j) 的值不这里是个关键点仔细看公式g(n, j) g(n, j-1) - f(P_j) * [ g(floor(n/P_j), j-1) - g(P_j-1, j-1) ]等式右边所有的g(..., j-1)都应该是上一轮的值。因此如果我们从大到小遍历i计算g(val[i], j)时g(floor(val[i]/P_j), j-1)这个值对应的下标idx其val[idx]一定小于等于val[i]。由于我们从大到小遍历下标idx可能大于i因为val数组是递减存储的值越小下标越大但g(val[idx], j)可能在本轮已经被计算更新了这就污染了我们需要用的“上一轮”的值。所以正确的做法是在每一轮j我们使用上一轮完整的g数组记为g_prev来计算本轮新的g数组记为g_curr。或者更节省空间的做法是只用一个g数组但从大到小遍历i时确保用到的g(floor(val[i]/P_j))是本轮尚未被覆盖的旧值。由于floor(val[i]/P_j) val[i]且val数组递减所以floor(val[i]/P_j)对应的下标k一定 i。如果我们从大到小i从m到1遍历那么当处理到i时下标k (i)的位置存储的还是上一轮的值因为k i我们还没处理到它。这样就保证了数据的正确性。这是Min_25筛实现中非常精妙且容易出错的一个循环顺序细节。4.3 递归计算S的优化与记忆化计算S(n, j)采用递归记忆化。记忆化的键值对(n, j)同样n只有O(sqrt(n))种可能可以用类似ind1/ind2的方法映射。j是质数序号范围是1到小于等于 sqrt(n)的质数个数。几个关键优化点边界剪枝if (n P[j]) return 0;质数剪枝if ((ll)P[j] * P[j] n) { ... // 直接返回质数部分贡献 }这个剪枝效果极好。预处理小范围当n比较小的时候比如n 1e6可以直接用线性筛预处理出f(i)的前缀和在递归中直接O(1)返回。这能避免大量递归到最底层的情况。避免重复计算SP(n)SP(n)就是第一步中我们最终得到的g(n, maxj)。我们可以把它提前算好存储在sum_prime数组中同样离散化存储在递归中直接查询。4.4 “卡常”的终极手段微积分估算与循环展开当n大到1e11量级时即使是O(n^{3/4} / log n)的 Min_25筛也可能在时间边缘徘徊。此时需要一些“邪道”优化。整数除法优化代码中会出现大量的n / i和n / (n/i)。确保使用64位整数long long。在C中/运算符对于整数是直接截断的就是我们要的整除效果。预处理开方与质数sqrt(n)需要多次计算可以先算好存起来。质数表用线性筛预处理到sqrt(n)即可。内存访问连续化g数组、sum_prime数组等访问时尽量顺序访问利用CPU缓存。递归改迭代对于S(n, j)的计算递归形式直观但函数调用有开销。有一种用栈模拟递归的迭代版Min_25筛但代码极其复杂可读性差除非万不得已如对递归深度有严格限制的环境一般不建议使用。竞赛中通常递归版本足够。微积分估算复杂度Min_25筛的复杂度约为O(n^{3/4} / log n)。对于n1e10n^{3/4} 1e7.5 ≈ 3.16e7再除以log(1e10)≈23运算量级在1e6左右这是可接受的。但对于n1e11运算量级可能到1e7就需要非常精细的优化。这时可以分析递归树发现大部分时间花在j很小即用很小的质数去筛的阶段。可以尝试手动展开最外几层循环比如手动计算j1,2,3对应质数2,3,5时的贡献从而减少递归调用次数。这是一种非常硬核的优化需要对代码和算法有极深的理解。5. 完整解题框架与调试心得将莫比乌斯反演和 Min_25 筛结合解决这类“求和”题的完整框架如下解析题目定义f(n)明确题目所求。莫比乌斯反演或狄利克雷卷积化简将∑f(i)转化为∑g(d) * floor(n/d)的形式确定需要求前缀和的函数g(d)。分析g(d)的性质确认g(d)是否为积性函数在质数p、质数幂p^k处的表达式是什么这是使用 Min_25筛的前提。设计 Min_25 筛中的辅助函数完全积性函数f1(p)用于第一步筛质数。需要满足对于任意正整数a,bf1(ab)f1(a)f1(b)且f1(p) g(p)。通常g(p)是一个关于p的多项式我们可以将其拆成多个单项式如p^0, p^1, p^2对每个单项式分别进行第一步的筛法因为f1(p)p^k是完全积性的。最后再将结果线性组合起来。原积性函数g(p^k)用于第二步递归计算S。需要能快速计算g(p^k)的值。实现 Min_25 筛预处理sqrt(n)以内的质数。离散化得到val,ind1,ind2。实现第一步计算g数组滚动数组并得到sum_prime质数处g(p)的和。实现第二步递归计算S(n, 1)注意剪枝和记忆化。整合求解利用 Min_25 筛求出G(m) ∑_{i1}^{m} g(i)对于任意m floor(n/d)的值。然后使用数论分块计算∑ g(d) * floor(n/d)。调试心得与坑点数据溢出这是最大的坑。n在1e10级别n*n就会溢出64位。在计算P_j * P_j、P_k^{e1}时务必在乘法前判断是否超过n或LLONG_MAX或者使用__int128进行中间计算。边界条件f(1)的值根据题目定义处理。在 Min_25 筛中我们通常统计从2开始的数最后再加上f(1)。多项式拟合的系数当g(p)是多项式时比如g(p) p^2 p我们需要分别用f1_a(p)p^2和f1_b(p)p做两次第一步筛法得到sum_prime_a和sum_prime_b然后sum_prime sum_prime_a sum_prime_b。初始化g(n,0)时也要分别计算∑i^2和∑i的公式。记忆化S(n,j)的j维度j是质数下标范围不大可以直接作为数组第二维。但要注意当n很小但j很大时状态(n,j)可能不合法n P[j]记忆化数组需要初始化一个非法值如-1并在递归开头判断。验证先用小数据n1e6跑一遍 Min_25 筛结果与线性筛暴力计算的结果对比。再用中等数据n1e8测试确保在可接受时间内结果正确。最后挑战大数据。这道“国赛模拟”题就像一场综合性的登山训练。莫比乌斯反演是规划路线图让你知道山在哪、方向在哪Min_25筛是攀登陡峭岩壁的专业装备和技术而“卡常”则是调整呼吸、优化每一个动作确保你在体力耗尽前登顶。整个过程充满挑战但一旦走通你对数论算法和代码优化的理解将会达到一个新的层次。