1. 从一道经典题说起为什么我们需要整除分块如果你刷过一些算法题或者对计算数学感兴趣大概率见过下面这个问题给定一个正整数n求∑_{i1}^{n} ⌊n/i⌋的值。这里的⌊x⌋表示对x向下取整。一个最直接的想法是写一个循环从i1到n累加n//i//表示整数除法。这在n比较小的时候比如n10完全没问题。但当n达到10^9甚至10^{12}这个量级时这个O(n)的算法就彻底失效了程序会运行到天荒地老。问题的核心在于当我们计算⌊n/i⌋时随着i的增大这个值的变化并不频繁。例如当n10时i1:⌊10/1⌋ 10i2:⌊10/2⌋ 5i3:⌊10/3⌋ 3i4,5:⌊10/4⌋ 2,⌊10/5⌋ 2i6,7,8,9,10:⌊10/6⌋ 1, ...,⌊10/10⌋ 1你会发现⌊n/i⌋的值会“成块”地出现。i4和i5时结果都是2i6到i10时结果都是1。整除分块也叫数论分块正是利用了这种“值相同”的连续性将原本需要n次计算的过程压缩到大约2√n次计算时间复杂度从O(n)骤降到O(√n)。这对于处理大数据量是颠覆性的提升。今天我们就来彻底拆解这个强大而优雅的工具让你不仅会用更懂其背后的数学原理和实战中的各种“坑”。2. 核心原理值域如何“分块”要理解整除分块关键在于弄清楚对于给定的n当i在[1, n]范围内变化时⌊n/i⌋的哪些取值会连续出现以及每个相同的取值会持续多长的一段i2.1 直观理解与数学推导我们设k ⌊n/i⌋。这意味着k是整数且满足k ≤ n/i k1。对这个不等式进行变换由k ≤ n/i可得i ≤ n/k。由n/i k1可得i n/(k1)。因此对于同一个k满足⌊n/i⌋ k的i的取值范围是( n/(k1), n/k ]由于i是正整数所以i的取值范围实际上是i ∈ [ ⌊n/(k1)⌋ 1, ⌊n/k⌋ ]这就是分块的本质对于每一个可能的商k都对应了一段连续的i。我们不需要遍历每一个i只需要找到每一块的起点l和终点r然后一次性计算这一整块的贡献贡献值 k * (r - l 1)。2.2 如何高效地找到每一块的边界在实际编程中我们通常不是通过k来推导i的范围而是直接通过i来跳转。算法流程如下初始化l 1总和ans 0。当l ≤ n时进入循环 a. 计算当前l对应的商k n // l。 b.找到当前块的右边界r这是最关键的一步。对于商为k的这一块最大的i是多少根据前面的推导就是r n // k。因为i最大可以取到⌊n/k⌋。 c. 累加当前块的贡献ans k * (r - l 1)。 d. 将l跳到下一块的起点l r 1。循环结束ans即为所求。注意这里r n // k的推导是整除分块的核心。你可以这样记忆k n // l那么使得n // i仍然等于k的最大i就是n // k。可以自己用n10, l4(k2) 验证一下r 10//2 5正是我们之前观察到的块边界。2.3 复杂度为什么是 O(√n)我们来粗略估计一下块的数量。当i ≤ √n时⌊n/i⌋至少有√n种不同的取值因为i不同商很可能不同。当i √n时⌊n/i⌋的值必然小于√n因此最多也只有√n种不同的取值。所以总的块数不会超过2√n个。这意味着我们只需要进行大约2√n次迭代而不是n次。3. 基础模板与代码实现理解了原理代码实现就非常直观了。下面给出 Python 和 C 的模板用于计算∑_{i1}^{n} ⌊n/i⌋。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 # 测试 print(floor_sum(10)) # 输出: 27 # 验证: 10532211111 27#include iostream using namespace std; 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); } return ans; } int main() { cout floor_sum(10) endl; // 输出 27 return 0; }实操心得在代码中变量命名使用l(left),r(right),k(quotient) 比用i, j, t等更清晰有助于在复杂问题中理清思路。另外注意数据范围当n很大时如10^12累加结果ans可能会超过 32 位整数范围务必使用long long(C) 或 Python 的默认大整数。4. 整除分块的威力解决更复杂的问题如果整除分块只能解决∑ ⌊n/i⌋那它的价值就大打折扣了。它的真正威力在于能够处理求和项中包含⌊n/i⌋的各种函数。通用形式为∑_{i1}^{n} f(i) * g(⌊n/i⌋)。4.1 经典例题一∑ i * ⌊n/i⌋问题计算S ∑_{i1}^{n} i * ⌊n/i⌋。思路解析 在每一块[l, r]内⌊n/i⌋的值是常数k。因此这一块对总和的贡献是贡献 k * ∑_{il}^{r} i而∑_{il}^{r} i是一个等差数列求和等于(l r) * (r - l 1) / 2。代码实现def sum_i_times_floor(n): ans 0 l 1 while l n: k n // l r n // k # 等差数列求和: (首项 末项) * 项数 / 2 sum_i (l r) * (r - l 1) // 2 ans k * sum_i l r 1 return ans # 测试 n5: 1*5 2*2 3*1 4*1 5*1 5434521 print(sum_i_times_floor(5)) # 输出: 214.2 经典例题二∑ ⌊n/i⌋²问题计算S ∑_{i1}^{n} ⌊n/i⌋²。思路解析 同样在每一块内⌊n/i⌋是常数k。这一块的贡献是贡献 k² * (r - l 1)只需要在基础模板上将累加项从k改为k * k即可。代码实现def sum_floor_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注意事项这里k*k可能导致中间结果溢出。在 C 中即使k是long longk*k也可能溢出。安全的做法是使用__int128或在乘法前进行转换ans (long long)k * k * (r - l 1)。Python 则无需担心。4.3 实战应用莫比乌斯反演的前缀和计算整除分块在数论中一个至关重要的应用是快速计算某些数论函数的前缀和例如∑_{i1}^{n} ⌊n/i⌋ * ⌊m/i⌋。这在莫比乌斯反演题目中极为常见。问题给定n, m求S ∑_{i1}^{min(n, m)} ⌊n/i⌋ * ⌊m/i⌋。思路解析 我们不能直接对i分块因为⌊n/i⌋和⌊m/i⌋的块边界可能不同。但我们可以取两个块边界的较小值作为当前块的真正右边界。算法步骤令up min(n, m)。初始化l1, ans0。当l up时 a. 计算k1 n // l,k2 m // l。 b. 计算r1 n // k1,r2 m // k2。 c.当前块的右边界r min(r1, r2, up)。这是关键必须保证i在[l, r]内时⌊n/i⌋和⌊m/i⌋都保持不变。 d. 累加贡献ans k1 * k2 * (r - l 1)。 e.l r 1。代码实现def sum_floor_product(n, m): ans 0 l 1 up min(n, m) while l up: k1, k2 n // l, m // l r1, r2 n // k1, m // k2 r min(r1, r2, up) ans k1 * k2 * (r - l 1) l r 1 return ans这个技巧是解决许多莫比乌斯反演题目的关键一步能将复杂度从O(n)降至O(√n)。5. 边界处理与易错点剖析整除分块的逻辑虽然清晰但边界情况处理不当极易出错尤其是在竞赛或工程代码中。5.1 右边界r可能超过n在计算r n // k时当k0时会出现问题。但k n // l只要l ≤ nk至少为 1所以不会出现除零错误。然而在双变量如n, m情况下当我们取min(r1, r2)时逻辑是安全的。唯一需要注意的是循环条件l n必须严格遵守。5.2 数据类型与溢出这是最大的“坑”之一。中间结果溢出即使最终结果在long long范围内累加过程中的中间值k * (r-l1)也可能溢出。例如n1e10当l1时kn(r-l1)1乘积1e10在int范围内。但当l较小时(r-l1)可能很大接近n乘积k * length极易超出int甚至long long的范围。解决方案无脑使用long long。在 C 中对于n可能达到1e9级别的问题所有相关变量n, l, r, k, ans都应定义为long long。在 Python 中则无需担心。5.3 循环终止条件与l的更新必须确保l能正确跳到下一个位置并且循环能终止。更新语句l r 1是正确的。不能写成l r否则会陷入死循环下一轮循环的k和r不变。循环条件while l n是标准写法。在双变量问题中可能是while l up。5.4 当求和下标不是从1开始有时问题要求计算∑_{ia}^{b} ⌊n/i⌋。有两种处理方法转化为前缀和S(a, b) S(1, b) - S(1, a-1)。分别对两个前缀和用整除分块计算。修改分块起点直接从l a开始循环但在计算第一块的r时需要和b取最小值r min(n // k, b)。同时循环条件改为l b。方法1更通用且不易出错推荐使用。6. 性能对比与复杂度分析为了让你直观感受整除分块的性能提升我们做一个简单的实验。import time def naive_sum(n): O(n) 的朴素算法 s 0 for i in range(1, n 1): s n // i return s def block_sum(n): O(√n) 的整除分块算法 s 0 l 1 while l n: k n // l r n // k s k * (r - l 1) l r 1 return s # 测试 test_n 10**7 # 一千万 start time.time() res1 naive_sum(test_n) t1 time.time() - start print(f朴素算法: 结果{res1}, 耗时{t1:.4f}秒) start time.time() res2 block_sum(test_n) t2 time.time() - start print(f整除分块: 结果{res2}, 耗时{t2:.6f}秒) print(f速度提升倍数: {t1/t2:.0f}倍)在我的测试环境中n10^7输出大致如下朴素算法: 结果... 耗时0.45秒 整除分块: 结果... 耗时0.0002秒 速度提升倍数: 2000倍当n增大到10^10百亿时朴素算法已完全不可行而整除分块算法依然可以在毫秒级完成。这就是算法优化的魅力。7. 进阶技巧与变形掌握了标准形式后我们来看一些更灵活的用法。7.1 与数论函数结合例如计算∑_{i1}^{n} μ(i) * ⌊n/i⌋其中μ(i)是莫比乌斯函数。我们可以在线性筛法预处理出μ(i)的前缀和M(i)后利用整除分块快速计算∑_{il}^{r} μ(i) * k k * (M(r) - M(l-1))这样我们只需要O(√n)次前缀和查询而预处理前缀和是O(n)的。这是杜教筛等高级算法的基础思想之一。7.2 多维整除分块问题可以扩展到多维例如求∑_{i1}^{n} ∑_{j1}^{m} ⌊n/i⌋ * ⌊m/j⌋。这实际上可以分解为两个独立求和的乘积(∑ ⌊n/i⌋) * (∑ ⌊m/j⌋)分别用整除分块计算即可。但对于形如∑_i ∑_j ⌊n/i⌋ * ⌊m/j⌋ * [gcd(i,j)1][ ]为艾弗森括号的问题则需要结合莫比乌斯反演和整除分块是更复杂的组合。7.3 记忆化与预处理在一些题目中n可能很大但我们需要对多个不同的n查询∑ ⌊n/i⌋。如果直接对每个n都做一次O(√n)的分块总复杂度可能偏高。此时可以观察到一个性质对于i √NN是最大可能的n⌊n/i⌋的值域很小。可以预处理出所有k对应的f(k)然后根据n的大小选择是分块计算还是直接调用预处理结果这是一种典型的“根号分治”思想。8. 常见问题排查与调试技巧即使理解了算法自己实现时也可能遇到问题。这里分享几个调试技巧。问题1结果不对通常是少加或多加了一块。检查在循环内打印l, r, k的值。对于小的n如10手动计算每一块的贡献与程序输出对比。典型错误在计算块长度时误写成(r - l)而不是(r - l 1)。问题2程序陷入死循环。检查l的更新语句是否为l r 1循环条件是否为l n在双变量问题中右边界r是否计算正确特别是取min操作问题3处理大数时结果异常出现负数。检查100% 是溢出问题。确保所有变量包括循环变量、中间乘积都使用了足够大的数据类型C中用long long。在累加ans k * (r-l1)时考虑先强制转换ans (long long)k * (r-l1)。问题4如何验证结果的正确性对于中等规模的n如n ≤ 10^6写一个朴素的O(n)算法作为暴力对照确保分块算法的结果与之一致。这是最可靠的验证方法。一个简单的调试示例def debug_floor_sum(n): ans 0 l 1 print(fn {n}) print(块号 | 左边界l | 右边界r | 商k | 块长度 | 贡献) print(- * 50) block_id 1 while l n: k n // l r n // k length r - l 1 contribution k * length ans contribution print(f{block_id:4} | {l:7} | {r:7} | {k:4} | {length:6} | {contribution:8}) l r 1 block_id 1 print(f\n总和 ans {ans}) return ans debug_floor_sum(10)运行这个函数你可以清晰地看到每一块是如何被划分和计算的非常适合初学者理解算法流程。整除分块是一个将数学观察转化为高效算法的典范。它看起来像是一个“技巧”但其背后是严谨的数学推导和对问题结构的深刻洞察。掌握它不仅能让你在遇到相关题目时游刃有余更能提升你分析问题、寻找规律的能力。下次再看到包含⌊n/i⌋的求和式不妨先想想能不能分块这往往是通往高效解法的第一扇门。