先问自己一个看似简单、但第一次做多半会绕进去的问题给你一个 n10要求算出前 10 个正整数所有因数之和的总和也就是 sigma(1)sigma(2)...sigma(10)。最直接的做法无非是每个数都去试除把所有约数找齐再加起来。可一旦 n 从 10 变成 1e7甚至 1e12这种“直接做法”会慢到让你怀疑人生。我最初接触这类题时也在“暴力枚举”上栽过跟头后来才发现同一个求和问题换一个视角复杂度可以从 O(n√n) 一路降到 O(√n)而且代码量并不增加太多。这篇文章想把这条完整的思路链路写清楚先定义清楚“前 n 个数因数和”到底在算什么再给出三种可落地的方案最后对比它们的使用边界。适合正在刷算法题、做数学编程练习或者纯粹对数论感兴趣的读者。1. 先把问题说清楚前 n 个数因数和的本质1.1 因数和 sigma(k) 的定义与计算示例对于任意正整数 k它的因数就是所有能整除 k 的正整数因数和 sigma(k) 就是这些因数的总和。比如k6因数有 1、2、3、6所以 sigma(6)12k10因数有 1、2、5、10所以 sigma(10)18k16因数有 1、2、4、8、16所以 sigma(16)31。所谓“前 n 个数的因数和”实际上就是计算S(n) sigma(1) sigma(2) ... sigma(n)。这是一个经典的数论求和问题也是很多算法竞赛和面试题里“因子相关”题目的基础。别小看这个定义光是“因数和”和“因数个数”的区别就足够让不少人翻车因数个数只关心有几个约数因数和关心的是所有约数的数值总和。一个常见的错误是把求因数个数的公式套到因数和上结果连测试样例都过不了。1.2 三类方法的共同目标与复杂度轮廓求 S(n) 有三条典型技术路线它们的核心差异在于“把贡献来源”放在哪里从每个数出发找它的所有因数并累加这是朴素枚举从每个因数出发统计它在前 n 个数里出现了多少次这是贡献法在贡献法基础上利用整除向下取整的取值分段把相同取值的区间合并计算这是整除分块。三种方法的适用边界完全不同n 很小时第一种最简单n 到千万级时第二种是主力n 到亿级以上甚至更大时第三种才是最终答案。我习惯在写题时把三种都留在脑子里因为不同题目的 n 上限差别极大选错方法就是直接的超时。2. 方法一朴素枚举O(n√n) 的“保底方案”2.1 枚举到 sqrt(k) 就够的原理最没技术含量的做法就是对每个 k 从 1 到 n枚举它的因数。但有一个关键优化不需要枚举到 k只需要枚举到 sqrt(k)。原因在于除数和商是成对出现的。如果 d 是 k 的因数那么 k/d 也一定是 k 的因数。比如 k12d1 时配对的是 12d2 配对的是 6d3 配对的是 4。当 d 从 1 增长到 sqrt(k) 时所有较小的那个因数都已经枚举过较大的那个通过 k/d 直接得到。唯一例外是平方数比如 k16d4 时 k/d4同一个因数不能重复加。这就是为什么枚举上界可以放心设置为 sqrt(k)而不是 k既减少了循环次数又不会漏掉任何因数。2.2 代码实现与复杂度验证用 C 写出来大概是这个样子long long solveByTrial(int n) { long long ans 0; for (int k 1; k n; k) { for (int d 1; (long long)d * d k; d) { if (k % d 0) { ans d; if (d * d ! k) ans k / d; } } } return ans; }我来验证一下 k10 这一轮的贡献d11 是因数加上 1 和 10d22 是因数加上 2 和 5d33 不是因数d*d10 在 d4 时停止。于是 sigma(10)1102518正确。这个方法的复杂度是 sum_{k1}^n sqrt(k)量级大约为 O(n√n)。具体算一下n1e5 时大约要枚举两千多万次C 可以轻松通过n1e7 时大约需要 300 亿次试除已经明显超时。所以它注定只能作为“小数据方案”。2.3 朴素方法的适用上限与改进动机虽然慢但我不建议你直接跳过它。理由有两个第一它实现极其简单几乎不可能写错是验证其他复杂算法的“对拍器”。拿一个随机生成的 n用朴素方法跑一遍结果再用优化方法跑一遍结果两边一致才能放心提交。第二它能帮助建立“因子成对出现”的直觉这是后面所有优化的起点。如果你连 sqrt(k) 这个上界都没想过后面理解贡献法和分块法会有困难。如果 n 超过 1e6朴素方法就已经开始吃力了。这时候需要换一个更巧妙的视角把“找每个数的所有因数”变成“统计每个因数出现了多少次”。3. 方法二因子贡献法把视角倒过来变成 O(n)3.1 核心观察把求和顺序交换重新看一遍我们要算的式子S(n) sum_{k1}^{n} sum_{d|k} d。这个双重求和里k 是被“遍历者”d 是“被求和的值”。如果我们把两个求和的顺序交换从 d 的角度看问题式子会变成S(n) sum_{d1}^{n} d * #{k | 1 k n, d|k}。也就是说对于每个正整数 d它在 1 到 n 的范围里作为因数被加进去多少次答案是它能整除的数 k 的个数也就是 1 到 n 中 d 的倍数的个数。这个个数恰好是 floor(n/d)。这个交换很关键它把一个“内层还要试除”的问题变成了一个“直接算倍数个数”的问题。打个比方你想统计一个班级里所有同学收到的生日礼物数量如果挨个同学翻礼物会很慢反过来统计“每件礼物覆盖了哪些人”效率反而更高。因子贡献法就是这个思路。3.2 代码实现与等比验证用这个公式写代码结构会非常简洁long long solveByContribution(int n) { long long ans 0; for (int d 1; d n; d) { ans (long long)d * (n / d); } return ans; }拿 n10 手动跑一遍d1 到 10 中 d 的倍数个数贡献 d * floor(10/d)110102510339428521061671781891910110这样累加得到 87和直接算 sigma(1)...sigma(10)1347612815131887 完全一致。复杂度从 O(n√n) 降到了 O(n)n 到 1e7 时在 C 里大约也就不到一秒的量级性能提升非常明显。3.3 为什么 O(n) 已经很快却还不是终点既然方法二已经是 O(n)为什么还要继续优化因为现实题目里 n 的取值并不总是那么“温柔”。如果 n 是 1e5方法二已经绰绰有余如果是 1e9方法二就需要跑十亿次循环哪怕 1ns 一次也要一秒多显然不够。更极端的情况是 n 到 1e12O(n) 直接不可行。这时候真正的突破口在于floor(n/d) 并不是每个 d 对应的值都不同它存在大段大段的“平台期”。只要我们能把这些相同取值的区间合并成一块来算复杂度就能进一步大幅下降。这就要引出第三种方法了。4. 方法三整除分块 等差数列压到 O(√n)4.1 floor(n/d) 的分段性与右端点推导先看一个具体的例子。n10 时floor(n/d) 的取值序列是10, 5, 3, 2, 2, 1, 1, 1, 1, 1。肉眼就能看出后面很长一段 d 对应的值都是 1。再仔细观察取值相同的 d 是连续的区间比如 d 从 4 到 5 都是 2从 6 到 10 都是 1。这种现象不是巧合对所有正整数 n 都成立floor(n/d) 是非递增的且相同值的 d 一定连续。假设当前从某个 dl 开始floor(n/l)q。那么这个 q 会持续到哪个位置设 r 是满足 floor(n/r)q 的最大整数。由 floor(n/r)q可得 r*q n同时 (r1)*q n进一步得到 r floor(n/q)。所以对于一个已知左端点 l区间右端点就是r n / (n / l)。也就是说d 从 l 到 r 的整段里floor(n/d) 的值都等于 q我们不需要逐个计算 d只需要计算这一段里所有 d 的“权和”再乘上 q。4.2 代码实现与 n10 的手算复查对于区间 [l, r]因为 q 是常数这一段的贡献为q * (l (l1) ... r) q * (l r) * (r - l 1) / 2。这里的 (l r) * (r - l 1) 一定是偶数因为两个相邻整数的乘积恒为偶数所以除以 2 不会产生小数。实现如下long long solveByBlock(int n) { long long ans 0; for (int l 1; l n; ) { int q n / l; int r n / q; ans (long long)q * (l r) * (r - l 1) / 2; l r 1; } return ans; }继续拿 n10 复查这段逻辑l1q10r10/101区间 [1,1]贡献 10*(11)*1/210l2q5r10/52区间 [2,2]贡献 5*(22)*1/210l3q3r10/33贡献 3*(33)*1/29l4q2r10/25贡献 2*(45)*2/218l6q1r10/110贡献 1*(610)*5/240。合计 10109184087完美对上。4.3 取模、溢出和边界条件的处理到这里方法三的主干已经成型。但实际写题时有几个坑非常值得注意。第一循环的次数不是 n而是大约 2*sqrt(n)。这很好理解q 取值大于 sqrt(n) 时区间数量不会超过 sqrt(n)q 取值小于等于 sqrt(n) 时q 本身最多只有 sqrt(n) 种取值。所以总体运行时间是 O(√n)。n1e9 时循环次数大约六万次n1e12 时大约两百万次这在绝大多数评测环境里都是秒过。第二计算 lr 或者中间乘积时容易超出 int 范围。n1e12 时l 和 r 都可能接近 1e12lr 接近 2e12再乘上 q 更会突破 64 位整数的安全边界。所以题目如果要求输出真实值要提前定位答案范围。实际上 S(n) 的量级大约等于 (π^2/12) * n^2 ≈ 0.822 * n^2。n1e6 时答案约 8e11用 long long 没问题n1e12 时答案约 8e23连 long long 都装不下这时候通常题目会要求取模。第三取模时不能简单地对每个因子取模后立即除以 2。因为取模之后的数不再是偶数直接除以 2 会破坏结果。我的做法是先判断 (lr) 和 (r-l1) 谁是偶数先除以 2 再相乘取模或者直接用支持大整数的类型计算乘积后再转回。如果语言支持 128 位整数也可以用 __int128 运算完再取模简单直接。第四注意 l 的更新是 r1而不是 l1。少了这一步整个分块就会退化成逐个枚举前功尽弃。5. 三种方法怎么选数据范围与场景对比5.1 复杂度与实现风格对照表三种方法各有各的适用场景放在一起对比会更直观方法时间复杂度空间复杂度适合的 n 范围参考代码难度朴素枚举O(n√n)O(1)n 1e5 左右低因子贡献法O(n)O(1)n 1e7 左右低整除分块O(√n)O(1)n 1e12 左右中注意我这里的边界只是经验值不是硬性标准。具体能跑多快取决于评测机速度、是否取模、语言选择等因素。Python 实现相同算法时常数更大O(n) 方法能承受的 n 就要再缩水不少。5.2 我个人的选型习惯与实测建议我自己写这类题时有一套固定顺序先看 n 和模数。如果没有模数且答案会非常大先把答案类型定为 long long必要时换大数或不强求真实值n 在 1e5 以内直接上朴素枚举代码最快思路最清晰n 在 1e7 左右又没有取模要求因子贡献法最稳n 更大别犹豫直接整除分块。很多初学者会觉得方法三一定比方法二“高级”所以任何题都套分块公式。其实方法二的优势是代码更易读、不容易写错遇到同样能用 O(n) 解决的问题没必要硬上更复杂的分块。只有 n 确实大到 O(n) 无法承受时分块的价值才体现出来。还有一点很重要写分块之前务必准备好一份朴素的暴力实现。我每次写方法三都会先写一个 solveByTrial(100) 之类的函数拿 n100、n1000、n10000 的随机小数据对拍确认两边结果一样才敢提交。这种习惯帮我挡下了至少两次因边界处理错误导致的 WA。6. 延伸一步预处理所有因数和与一些踩坑记录6.1 倍数标记与线性筛的思路如果你遇到的是多次查询而每次的 n 都不同比如题目要回答一堆 [1, N] 范围内的因数和那么上面的“单点计算”方法就不太划算了。这时可以先预处理出 sigma(1) 到 sigma(n) 的完整数组再做一次前缀和。最简单的预处理方法是倍数标记。开一个长度为 n1 的数组 dsum初始全为 0然后for (int i 1; i n; i) { for (int j i; j n; j i) { dsum[j] i; } }这个双层循环的复杂度是 O(n log n)因为内层总执行次数是 n/1 n/2 ... n/n ≈ n log n。当 n1e6 时大约一千多万次操作完全可接受n1e7 时接近一亿多次C 也能勉强跑完。预处理完毕后对 dsum 做前缀和每次查询 O(1) 返回答案。如果想要更快的 O(n) 预处理可以用线性筛的思路在筛选过程中维护每个数的最小质因子以及去掉最小质因子之后的部分配合约数和公式逐步生成 sigma 数组。这个实现比倍数标记复杂不少但思路本质不变递推而不是重新计算。6.2 实际做题最容易踩的几个坑最后把我踩过、也见过别人踩的坑集中列一下省得你重复踩枚举因数的上界写成 ddk但 d 是 intk 很大时 dd 会溢出变成负数导致死循环。应该写成 (long long)d*d k或者 d k / d。平方数处理失误。很多人在 d*dk 时还机械地加上 k/d导致平方数的因数被重复累加结果比真实答案大一圈。分块公式里忘记先判断奇偶就直接对取模结果除 2。我在一次需要取模的题目里就这么翻过车后来改成先把 (lr) 或 (r-l1) 中偶数项除 2 再做乘法取模。答案类型用了 int。S(n) 增长非常快n 稍大一点就会超过 20 亿建议一开始就写 long long。分块循环时 l 更新为 r1有人手误写成 l区间没有提出来复杂度又变成了 O(n)。回想我自己刚开始做这类题时也是从纯暴力逐步摸索到分块方案的。那时的体会是这题真正难的不是最后公式而是能否意识到“把计算顺序颠倒过来”这个念头。如果你读完这篇内容能把“交换求和顺序”和“整除值分段”这两个思维工具用到别的题目里那就不只是会算因数和而已。以后遇到约数个数之和、欧拉函数前缀和一类的问题你会发现底层的套路是相通的。