1. 从一道经典面试题说起为什么暴力求和会超时很多朋友在刷算法题或者准备面试时都遇到过类似这样的问题给定一个正整数n求∑_{i1}^{n} ⌊n/i⌋。这里的⌊x⌋表示对x向下取整。新手的第一反应往往是写一个简单的循环def naive_sum(n): total 0 for i in range(1, n 1): total n // i return total这个解法逻辑清晰完全符合题意。当n比较小比如n10时计算结果是10532211111 27完全正确。问题在于当n的规模变大比如n10^12时这个O(n)的算法就彻底失效了。循环10^12次即使每次只做一次除法在现代计算机上也需要难以接受的时间。那么有没有更快的办法仔细观察这个求和公式∑ ⌊n/i⌋你会发现一个有趣的现象随着i的增大⌊n/i⌋的值并不是每个i都不同而是会连续出现很多相同的值。比如当n10时i1⌊10/1⌋ 10i2⌊10/2⌋ 5i3⌊10/3⌋ 3i4, 5⌊10/4⌋ ⌊10/5⌋ 2i6, 7, 8, 9, 10⌊10/6⌋ ... ⌊10/10⌋ 1看从i6到i10这连续的5个数计算出的⌊n/i⌋都是1。如果我们能一次性算出这个“值相同的连续区间”的长度然后用值 * 区间长度来求和岂不是能跳过中间很多次重复计算这个思想就是整除分块的核心。它还有一个更形象的名字叫做数论分块。它的目标就是把1到n这n个数根据⌊n/i⌋的值是否相同分成若干个连续的块在每个块内⌊n/i⌋的值是恒定不变的。这样我们只需要遍历这些“块”而不是遍历每一个i时间复杂度可以从O(n)骤降到O(√n)。2. 整除分块的核心原理如何找到块的边界理解了整除分块的思想接下来最关键的问题就是给定一个块的起始下标l我如何快速找到这个块的结束下标r换句话说对于多大的i⌊n/i⌋的值还能和⌊n/l⌋保持一致我们设当前块的值为k ⌊n/l⌋。我们要找最大的r使得对于所有i ∈ [l, r]都有⌊n/i⌋ k。因为⌊n/i⌋ k根据向下取整的定义这意味着k ≤ n/i k1我们对不等式n/i k1进行变换n/i k1 i n/(k1)注意这里除的是k1一个正数不等式方向不变又因为i是整数且i要尽可能大同时满足⌊n/i⌋ k所以最大的i即r应该满足i ≤ n/k且i n/(k1)。更精确的r就是⌊n/k⌋。我们来推导一下由k ≤ n/i可得i ≤ n/k。所以r最大不能超过⌊n/k⌋。同时为了保证对于i r1值开始变化我们需要⌊n/(r1)⌋ k这等价于r1 n/k不更准确地说当i增加到⌊n/k⌋ 1时n/i就会小于k从而⌊n/i⌋变为k-1或更小。因此一个简洁而正确的结论是如果当前块的起始下标是l对应的值为k ⌊n/l⌋那么这个块的结束下标r就是⌊n / k⌋。让我们用n10, l6来验证一下。k ⌊10/6⌋ 1。那么r ⌊10 / 1⌋ 10。这意味着从i6到i10值都是1。正确。再验证n10, l4。k ⌊10/4⌋ 2。r ⌊10 / 2⌋ 5。检查i4,5时⌊10/4⌋2,⌊10/5⌋2。i6时值变为1。正确。所以整除分块的算法框架就出来了初始化l 1总和ans 0。当l ≤ n时循环 a. 计算当前块的值k n // l。 b. 计算当前块的右边界r n // k。这里r有可能超过n吗不会因为k ≥ 1所以r n // k ≤ n。 c. 这个块对总和的贡献是k * (r - l 1)将其加到ans上。 d. 将l更新为r 1准备处理下一个块。循环结束返回ans。这个算法的时间复杂度是多少关键在于l的更新方式l r 1而r n // (n // l)。可以证明l的取值大约只有2√n种具体证明涉及i和n/i的对称性。因此总的时间复杂度是O(√n)。对于n10^12√n 10^6百万级别的循环在现代计算机上瞬间即可完成相比10^12的暴力循环这是天壤之别。3. 整除分块的代码实现与细节剖析理论清晰了代码实现就非常直观。这里以 Python 为例给出一个标准的整除分块求和函数def floor_sum(n): 计算 ∑_{i1}^{n} ⌊n/i⌋ ans 0 l 1 while l n: k n // l # 当前块的值 r n // k # 当前块的右边界 ans k * (r - l 1) l r 1 # 跳到下一个块的起点 return ans代码简洁得令人惊讶但其中蕴含的细节和可能踩的坑才是我们作为开发者需要关注的。细节一为什么r n // k是安全的在循环中k n // l。当l很小时k可能很大。例如n100, l1时k100。计算r n // k 100 // 100 1。这符合预期第一个块[1, 1]的值是100。这里k作为除数它至少为1所以n // k这个整数除法是安全的不会除零。这是算法正确性的一个隐含保障。细节二循环的终止条件与数值范围循环条件是l n。当l逐渐增大k逐渐减小。最后一个块的值k通常会等于1。此时r n // 1 n。所以最后一个块会从某个l一直延伸到n。更新l r 1 n 1后循环条件l n不再满足循环结束。这个过程对int类型的n是完美的。但需要注意在l和r的计算中要确保使用能容纳n的整数类型在 Python 中自动处理在 C/Java 中需注意使用long long。细节三一个常见的错误实现有些初学者可能会尝试这样找r# 错误示范 r l while r 1 n and n // (r 1) k: r 1这个逻辑在数学上是正确的但它又退化成了O(n)的算法因为最坏情况下比如值连续为1的漫长区间它还是需要一步一步地移动r。我们之所以需要整除分块就是为了避免这种线性扫描。r n // k这个公式是O(1)的是效率提升的关键。让我们用一个具体的例子来跟踪一下算法过程加深理解。设n20。轮次l(起始)k 20 // l(值)r 20 // k(结束)区间[l, r]贡献k*(r-l1)更新后l11201[1, 1]20 * 1 20222102[2, 2]10 * 1 1033363[3, 3]6 * 1 644454[4, 4]5 * 1 555545[5, 5]4 * 1 466636[6, 6]3 * 1 3777210[7, 10]2 * 4 811811120[11, 20]1 * 10 1021总和 20106543810 66。可以暴力验证结果正确。整个过程只循环了8次而n20√20≈4.47循环次数在2√n的量级内。4. 整除分块的威力延伸解决更复杂的问题整除分块绝不仅仅用于求∑ ⌊n/i⌋这一个公式。它的本质是一种优化技巧用于处理所有包含⌊n/i⌋的、且需要对i从1到n求和或求积等的问题。只要求和项可以写成f(⌊n/i⌋)的形式并且f(x)可以快速计算那么就可以用整除分块将复杂度从O(n)降为O(√n)。场景一求∑_{i1}^{n} ⌊n/i⌋^2这很简单只需要修改贡献的计算方式。在原来的代码里贡献是k * (r - l 1)。现在贡献变成了k * k * (r - l 1)。def floor_sum_square(n): ans 0 l 1 while l n: k n // l r n // k ans k * k * (r - l 1) # 仅修改了这一行 l r 1 return ans场景二洛谷 P2261 [CQOI2007] 余数求和这是一道非常经典的整除分块应用题。题目要求计算G(n, k) ∑_{i1}^{n} k mod i。 我们知道k mod i k - i * ⌊k/i⌋。所以G(n, k) ∑_{i1}^{n} (k - i * ⌊k/i⌋) n*k - ∑_{i1}^{n} (i * ⌊k/i⌋)。现在问题转化为求∑_{i1}^{n} (i * ⌊k/i⌋)。注意这里求和上限是n但参与除法的是k。我们依然可以分块但块的边界由⌊k/i⌋决定且i的范围受n限制。我们需要对整除分块模板做一个调整def mod_sum(n, k): 计算 ∑_{i1}^{n} (k mod i) ans n * k l 1 # 注意循环条件既要 l n也要保证能形成有效的块即 k//l 0 while l n: if k // l 0: # 当 i 很大时⌊k/i⌋ 0后面所有的项都是0可以直接跳出 # 实际上当 l k 时k//l 就等于0 break cur_k k // l # 关键点块的右边界 r 由两个条件决定 # 1. 根据公式r k // cur_k # 2. i 不能超过 n r min(n, k // cur_k) # 计算 ∑_{il}^{r} i * cur_k cur_k * ∑_{il}^{r} i # 等差数列求和∑_{il}^{r} i (l r) * (r - l 1) // 2 sum_i (l r) * (r - l 1) // 2 ans - cur_k * sum_i l r 1 return ans这里的min(n, k // cur_k)是易错点。因为我们的i只求和到n所以块的右边界不能超过n。同时当l k时cur_k 0后面所有的k mod i都等于k这部分可以直接用k * (n - l 1)算出但更简单的做法是像上面代码一样当k // l 0时后面的i都满足⌊k/i⌋0所以∑ i * ⌊k/i⌋ 0对答案没有影响可以直接跳出循环。这个细节在解题时至关重要忽略了会导致结果错误。场景三与数论函数结合例如求约数个数和数论中有一个经典公式n以内所有数的约数个数之和D(n) ∑_{i1}^{n} ⌊n/i⌋。 为什么呢考虑1到n每个数它对约数个数和的贡献。数字i是哪些数的约数是i, 2i, 3i, ...直到⌊n/i⌋ * i。所以i作为约数出现的次数正好是⌊n/i⌋。因此∑_{i1}^{n} ⌊n/i⌋就等于所有数的约数个数和。看我们又回到了最初的公式。用整除分块可以在O(√n)时间内求出D(n)这在处理大数据时非常有用。更进一步许多数论函数的前缀和都可以通过杜教筛或洲阁筛等高级技巧结合整除分块来加速计算。在这些算法中整除分块是构建递归关系、进行状态转移的基础组件。可以说掌握了整除分块就打开了一扇通往高效数论计算的大门。5. 实战中的边界处理与性能优化在实际编码尤其是参加算法竞赛时整除分块的实现虽然短小但边界情况处理不当极易导致错误。下面分享几个我踩过坑后总结的经验。坑一数据类型的溢出这是最隐蔽的坑。看这段贡献计算代码ans k * (r - l 1)。当n很大比如10^12时k在初始阶段也很大接近10^12(r - l 1)也可能是一个很大的数最大可以达到n。这两个大数相乘很可能超出int甚至long在C/Java中是64位的范围。在 Python 中整数是任意精度的所以没问题。但在 C 中你必须使用long long来存储ans、k、(r-l1)以及它们相乘的中间结果。// C 正确示例 long long floor_sum(long long n) { long long ans 0; for (long long l 1, r; l n; l r 1) { long long k n / l; r n / k; ans k * (r - l 1); // k 和 (r-l1) 都是 long long } return ans; }坑二循环变量的更新与死循环在while循环中更新语句是l r 1。你必须确保r在每次循环中至少等于l。根据公式r n // (n // l)因为n // l 1所以r l是成立的。但在某些特殊的变形中比如求和上限m和除数n不同如果处理不当可能会出现r l的情况导致l无法增加陷入死循环。一个良好的习惯是在计算完r后显式地r max(r, l)确保其不小于l。坑三当n为 0 时的处理虽然题目通常给定n 1但在一些函数式编程或库函数设计中需要考虑n0的情况。根据定义∑_{i1}^{0}是空和结果为0。我们的循环条件l n在n0时不成立所以函数会直接返回初始值0。这是正确的行为。但如果你在函数开头加了if n 0: return 0的特判也完全没问题更清晰。性能优化小技巧对于单纯的∑ ⌊n/i⌋算法已经是O(√n)优化空间不大。但在一些嵌套分块或复杂函数计算中我们可以做点微优化使用for循环代替while在某些语言中for循环的 overhead 略小于while。可以将模板写成def floor_sum(n): ans 0 l 1 while l n: k n // l r n // k ans k * (r - l 1) l r 1 return ans也可以写成等价的for循环形式但可读性稍差。避免重复计算在计算贡献k * (r - l 1)时(r - l 1)就是区间长度。如果这个值在后续逻辑中还要用到可以存下来。对称性对于∑_{i1}^{n} ⌊n/i⌋当i √n时⌊n/i⌋的值都小于√n且每个值出现的次数很多。有些实现会分别处理i √n和i √n两部分但代码会复杂一些通常收益不大。标准的分块写法已经足够高效和简洁。6. 从整除分块到数论直觉理解其几何意义要真正内化整除分块不妨从几何角度来理解它。考虑函数f(i) n / i不是向下取整。这是一个反比例函数图像是一条下降的曲线。⌊n/i⌋就是这条曲线向下取整后的阶梯函数。当我们画出y n / i和y ⌊n/i⌋的图像时可以把i看成连续变量会发现⌊n/i⌋的图像是由一系列“平台”即值相等的区间组成的。每个平台对应一个整数值k平台的宽度即i的范围就是满足k ≤ n/i k1的i的区间长度。而整除分块算法就是在高效地找出所有这些平台的起止点。这个几何视角有助于我们解决一些变种问题。例如如果要求∑_{i1}^{n} ⌈n/i⌉向上取整该怎么办我们可以利用关系⌈n/i⌉ ⌊(n i - 1)/i⌋ ⌊(n-1)/i⌋ 1。这样就把向上取整转化为了向下取整可以继续套用分块。另一个重要的直觉是关于块的数量。为什么块的数量是O(√n)级别的考虑i从1到√n⌊n/i⌋的值从n降到大约√n这大约有√n个不同的值。当i从√n到n⌊n/i⌋的值从大约√n降到1每个整数值k从1到√n都对应一个区间。所以总块数大约是2√n。这个直觉在很多复杂度分析中都很管用。7. 在算法竞赛与工程中的应用实例整除分块在算法竞赛中属于基础数论知识常用于解决需要优化枚举的问题。除了前面提到的余数求和再举几个例子例1CF 1730B. Sum of Floor of Linear题目要求计算∑_{i0}^{n} ⌊(a*ib)/m⌋。这是一个更一般的线性函数向下取整求和。它可以通过类欧几里得算法或者另一种形式的分块来解决其思想与整除分块一脉相承都是寻找值相等的连续区间。例2求 ∑_{i1}^{n} d(i) 其中 d(i) 是 i 的约数个数。这就是我们之前推导的D(n) ∑ ⌊n/i⌋。直接应用整除分块即可。例3Project Euler 第 153 题寻找高斯整数约数和等问题中常常需要计算形如∑_{a1}^{n} ∑_{b1}^{n} [gcd(a,b)k]的式子经过莫比乌斯反演后经常会得到包含⌊n/i⌋的项这时整除分块就能派上用场将双重循环优化为O(√n)级别。在工程领域整除分块的应用相对较少因为它主要解决的是精确数学计算问题。但在一些需要高性能数学计算的库中例如某些密码学库或数学软件当需要计算大量类似的向下取整求和时可能会采用这种优化。更多时候它是作为一种经典的算法思想锻炼我们寻找规律、优化枚举的能力。理解整除分块不仅仅是学会了一个模板更重要的是掌握了“通过观察值的连续性将线性枚举优化为按块处理”的思想。这种思想在算法设计中非常普遍。例如在单调栈、滑动窗口等问题中我们都在利用数据的某种连续性或单调性来避免不必要的计算。整除分块正是这种思想在数论领域的一个完美体现。下次当你看到一个需要对1到n进行枚举且枚举项与⌊n/i⌋相关的题目时你的第一反应就应该想到能不能分块