整除分块算法：从O(n)到O(√n)的质变优化原理与实战

1. 从一道经典面试题说起为什么需要整除分块如果你刷过一些算法题或者对编程竞赛稍有了解大概率见过下面这个题目或者它的变种给定一个正整数n求∑_{i1}^{n} ⌊n / i⌋的值。其中⌊x⌋表示对x向下取整。比如n 5那么我们需要计算⌊5/1⌋ ⌊5/2⌋ ⌊5/3⌋ ⌊5/4⌋ ⌊5/5⌋ 5 2 1 1 1 10。初看之下这题简单得令人发指。一个for循环从1遍历到n累加n / i的整数部分时间复杂度是O(n)。当n比较小比如n 10^6时这个解法完全可行甚至可以说是标准答案。但问题往往就出在这个“小”字上。在实际的算法竞赛或者后端系统的高频计算中n的规模常常是10^9、10^{12}甚至更大。O(n)的复杂度在n10^{12}时意味着需要执行一万亿次循环这显然是不可接受的程序会超时到地老天荒。这时一个敏锐的观察者可能会发现这个求和序列⌊n/i⌋的值并不是每个i都不同。相反很多连续的i会得到相同的⌊n/i⌋值。以n10为例i12345678910⌊10/i⌋10532211111可以看到当i4,5时结果都是2当i6,7,8,9,10时结果都是1。如果我们能一次性算出所有结果为2的i的范围以及所有结果为1的i的范围那么就不用逐个i去计算了。我们只需要计算每个“值块”的值和这个值对应的下标范围长度然后将值 * 长度累加起来即可。这种将具有相同⌊n/i⌋值的连续i分成一块然后进行批量计算的思想就是整除分块也叫数论分块。它的核心价值在于能将许多涉及向下取整求和的算法复杂度从O(n)优化到O(√n)。这是一个质的飞跃让处理大规模数据成为可能。接下来我们就深入拆解这个强大工具的原理、实现和那些容易踩进去的坑。2. 整除分块的核心原理值域的“平台期”与边界推导要理解整除分块关键在于弄清楚对于给定的n当i在1到n之间变化时⌊n/i⌋这个函数图像长什么样以及更重要的是相同的函数值会连续出现在哪个i的区间里2.1 函数图像的直观感受我们以n20为例画出y ⌊20/x⌋在x从1到20的散点图想象一下。你会发现这个图像像一个陡峭下降的“阶梯”当x很小1, 2, 3...时y的值很大但下降很快。当x变大后y的值变小并且会在一段连续的x区间内保持不变形成一个“平台”。随着x接近ny的值最终会稳定在1当x n/2时。这个“平台”现象就是整除分块能够成立的基础。我们的目标就是找出每一个“平台”即值相同的连续区间的起止下标。2.2 关键定理右端点的计算公式设当前“平台”的值为k ⌊n / l⌋其中l是这个区间的左端点。那么这个值为k的区间右端点r是多少一个直观但不严谨的想法是只要⌊n / i⌋还等于ki就可以继续向右扩展。换句话说我们需要找到最大的i使得⌊n / i⌋ k。因为k ⌊n / l⌋根据向下取整的定义我们有k ≤ n / l k 1对于区间内的任意i要满足⌊n / i⌋ k等价于k ≤ n / i k 1。我们对k ≤ n / i两边取倒数注意k,n,i均为正数不等式方向不变并整理i ≤ n / k再对n / i k 1两边处理n / i k 1i n / (k 1)综合起来满足⌊n / i⌋ k的i需要满足n / (k 1) i ≤ n / k由于i是整数那么能取到的最大整数i就是⌊n / k⌋。重要推导结论如果当前区间的左端点是l对应的值是k ⌊n / l⌋那么这个区间的右端点r就是⌊n / k⌋。这个结论是整除分块算法的基石。它告诉我们不需要一个个i去试探可以直接通过左端点和当前值计算出整个区间的范围。2.3 复杂度为什么是 O(√n)这是整除分块最精妙的地方。我们来看k ⌊n / i⌋的可能取值。当i ≤ √n时k的取值至少有√n种因为i有√n种。当i √n时由于k ⌊n / i⌋且i √n那么k √n。所以k的取值也少于√n种。因此⌊n / i⌋的不同取值个数不会超过2√n个。这意味着无论n有多大我们最多只需要处理大约2√n个“块”。所以整个算法的时间复杂度是O(√n)。从O(n)到O(√n)在n10^12时计算量从一万亿次降到了两百万次左右这就是质变。3. 整除分块的算法实现与细节剖析理解了原理我们来看如何用代码实现。这里我会给出最清晰的实现模板并逐行解释每个细节的用意和可能遇到的坑。3.1 基础模板求解 ∑⌊n/i⌋我们先解决开篇提到的问题。假设n在long long范围内。long long solve(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; }这段不到10行的代码就是整除分块的核心。我们来拆解循环中的每一步初始化l 1从第一个数开始。计算当前值k n / l。在C/Java等语言中整数除法自动完成向下取整。计算右端点r n / k。这就是我们上一节推导出的关键公式。累加贡献这个区间[l, r]内所有的i其⌊n/i⌋都等于k。区间长度是(r - l 1)所以这个区间的总和是k * (r - l 1)。跳转到下一块下一个块的左端点就是当前块右端点的下一个位置即l r 1。一个关键细节为什么r n / k是安全的会不会导致r超过n 不会。因为k ⌊n/l⌋ ≥ 1所以n/k ≤ n。当k1时r n/1 n正好是最后一个块。3.2 模板的变种求解 ∑ i * ⌊n/i⌋问题升级求∑_{i1}^{n} i * ⌊n/i⌋。这不仅仅是求和值还要用下标i去加权。思路是一样的我们仍然找值相同的块[l, r]在这个块内⌊n/i⌋ k是常数。那么这个块对总和的贡献就是k * (l (l1) ... r) k * (l r) * (r - l 1) / 2这里用到了等差数列求和公式。代码只需要修改累加部分long long solve_weighted(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; // 等差数列求和首项l末项r项数(r-l1) ans k * (l r) * (r - l 1) / 2; } return ans; }注意除法的顺序在计算(l r) * (r - l 1) / 2时先乘后除可以避免整数除法的精度损失吗不能完全避免但在这个场景下(lr)和(r-l1)中必有一个是偶数所以先乘后除一定能得到整数结果。为了代码清晰和防止溢出有时会写成ans k * ((l r) * (r - l 1) / 2);。3.3 双重整除分块求解 ∑∑⌊n/(i*j)⌋更复杂的问题出现了求∑_{i1}^{n} ∑_{j1}^{m} ⌊n/(i*j)⌋。这里n,m都可能很大。暴力是O(n*m)不可行。一个自然的想法是先固定i对j使用整除分块。但这样复杂度是O(n * √m)当n也很大时依然不行。我们需要双重整除分块。观察⌊n/(i*j)⌋当i固定时j在某个区间内变化这个值可能不变同时当i变化时j的块边界也会变化。实现起来需要更精巧的循环。long long solve_double(long long n, long long m) { long long ans 0; long long min_nm min(n, m); for (long long i 1, i_r; i min_nm; i i_r 1) { i_r min(n / (n / i), m / (m / i)); // 关键 long long k1 n / i; long long k2 m / i; // 这里假设求和的是 ⌊n/i⌋ * ⌊m/i⌋需要根据具体公式调整 // ans ... (k1, k2, i, i_r); } return ans; }双重分块的核心在双重循环中i和j的块边界是相互制约的。i的右端点i_r必须同时满足⌊n/i⌋不变和⌊m/i⌋不变如果公式里涉及两个数。所以取min(n / (n / i), m / (m / i))作为公共的右边界。这是双重分块中最容易出错的地方必须仔细推导具体问题的边界条件。4. 整除分块的实战应用与边界陷阱整除分块不是一个孤立的算法它是解决许多数论和算法问题的利器。下面通过几个典型场景看看它如何大显身手以及在实际编码中那些“坑”藏在哪。4.1 应用一优化欧拉函数前缀和计算欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。有一个重要的求和公式∑_{d|n} φ(d) n但如果我们想求前缀和S(n) ∑_{i1}^{n} φ(i)有一个基于整除分块的经典推导∑_{i1}^{n} φ(i) ∑_{i1}^{n} ∑_{j1}^{i} [gcd(i, j) 1] 1/2 * (∑_{i1}^{n} ∑_{j1}^{n} [gcd(i, j) 1] 1)进而可以推导出S(n) (∑_{i1}^{n} μ(i) * ⌊n/i⌋² 1) / 2其中μ(i)是莫比乌斯函数。计算∑ μ(i) * ⌊n/i⌋²就可以用整除分块来优化前提是能快速得到莫比乌斯函数的前缀和。这是杜教筛等高级算法的基础组成部分。4.2 应用二莫比乌斯反演中的求和优化莫比乌斯反演公式常常将问题转化为形如∑_{i1}^{n} f(i) * ⌊n/i⌋的式子。例如求1到n中所有数的约数个数之和∑_{i1}^{n} d(i) ∑_{i1}^{n} ⌊n/i⌋看这就是我们最开始的问题直接整除分块O(√n)解决。而暴力求每个d(i)再累加是O(n√n)或O(n log n)。4.3 边界陷阱与调试技巧即使理解了算法实现时也常常翻车。下面是我踩过或见过的几个典型坑陷阱一整数溢出这是最大的坑。当n很大如1e12时l,r,k都需要用long longC或longJava。计算k * (r - l 1)时两个long long相乘可能溢出。例如n1e12k在i1时就是1e12乘以一个长度很容易超过2^63-1。解决方案是使用128位整数如GCC的__int128或在乘法前判断是否溢出或者使用带模的乘法。// 使用 __int128 防止溢出 ans (__int128)k * (r - l 1); // 或者在取模意义下 ans (ans (k % MOD) * ((r - l 1) % MOD)) % MOD;陷阱二循环终止条件与死循环模板中的循环条件是l n。但在某些变体问题中n可能不是上限或者r的计算公式可能出错导致r l从而使l r 1无法增长陷入死循环。务必在计算完r后用min(r, n)进行限制这是一个好习惯。r min(n / k, n); // 显式限制右边界不超过n陷阱三除零错误当k计算为0时r n / k就会除零。这会在什么时候发生当l n时n / l为0。但我们的循环条件是l n所以理论上不会进入l n的循环。然而在双重分块或复杂公式中如果k由其他计算得出必须警惕除零的可能。调试技巧打印每个块当你怀疑分块出错时最有效的调试方法是在循环内打印出l,r,k的值。for (long long l 1, r; l n; l r 1) { long long k n / l; r n / k; printf(Block: l%lld, r%lld, k%lld\n, l, r, k); // ... 累加逻辑 }检查1.l是否递增2. 每个[l, r]区间是否覆盖了所有1到n的数3. 对于区间内任意一个i手动计算n/i是否等于k5. 从整除分块到数论函数前缀和思想的延伸整除分块的价值远不止于计算一个简单的求和。它揭示了一种重要的优化思想通过识别函数值的“平台期”将线性枚举转化为批量处理。这种思想可以推广到许多数论函数的前缀和计算中。例如我们想求∑_{i1}^{n} f(⌊n/i⌋)其中f是一个计算复杂度较高的函数。如果直接算需要对每个i计算一次f成本是O(n * Cost(f))。使用整除分块我们只需要对每个不同的⌊n/i⌋值计算一次f成本降为O(√n * Cost(f))。更进一步在杜教筛、Min_25筛等快速计算积性函数前缀和的算法中整除分块是构建递归关系、进行状态转移的关键步骤。它帮助我们将求和范围从1...n划分成O(√n)个不同的⌊n/i⌋值从而将问题规模指数级降低。理解整除分块就像是掌握了一把打开许多中高级数论问题大门的钥匙。它要求的预备知识不多基本代数运算和编程循环但带来的效率提升是巨大的。下次当你看到求和符号∑和向下取整⌊⌋在一起时就应该条件反射般地想到能不能分块