imicola 整除分块
整除分块

整除分块

491 字 · 约 1 分钟

我们在这里主要聊的是 整除分块 ,这是求解形如

∑i=1nf(⌊ni⌋)\sum\limits^{n}_{i=1} f\left(\left\lfloor \frac{n}{i} \right\rfloor\right)
这类涉及到 整除 或 取整 的求和问题,其核心思想是:对于固定的nn,⌊ni⌋\left\lfloor \frac{n}{i} \right\rfloor的值在一定区间内是相同的,我们可以将这些 ii 连续区间优化为一次处理

对一个固定的 n ,我们考虑其表达式

k=⌊ni⌋k = \left\lfloor \frac{n}{i} \right\rfloor
当ii增大时, ni\dfrac{n}{i} 单调递减,故kk是单调不增的

对于某个确定的kk,所有满足⌊ni⌋=k\left\lfloor \frac{n}{i} \right\rfloor = k的i连续且可以用一个区间 [L,R][L,R] 表示

现在我们来求这个区间

{k=⌊ni⌋  ⟺  k≤ni<k+1  ⟺  nk+1<i≤nk\begin{cases} k = \left\lfloor \frac{n}{i} \right\rfloor \\ \iff k \le \frac{n}{i} < k+1 \\ \iff \frac{n}{k+1} < i \leq \frac{n}{k} \end{cases}
因此:
L=⌊nk+1⌋+1R=⌊nk⌋L = \left\lfloor \frac{n}{k+1} \right\rfloor + 1 \quad R = \left\lfloor \frac{n}{k} \right\rfloor
在遍历的时候我们更倾向于使用 RR

显然对于向上取整我们也可以使用整除分块来优化复杂度,我们可以转化为 ⌊n+i−1i⌋\left\lfloor \frac{n + i - 1}{i} \right\rfloor 来进行整除分块

遍历方法

整除分块的标准做法是:

从小到大遍历 ii ,一次跳过所有 n/i 相等的区间

模板

for(i64 l = 1,r;l <= n; l = r + 1){
	i64 k = n / i;
	r = n / k;
	// code for solution
}

// 对于向上取整
for(i64 l = 1,r;l <= n;l = r + 1){
	i64 k = (n + l - 1) / l;
	if(l == 1){
		r = 1;
	}
	else{
		r = max(n,(n - 1)/(k - 1));
	}
	// code here
}
cpp

一个例子,可以看下面计算约数计数和
Solution1

另外一种形式的分块

这种形式的分块主要是以下类型

∑i=1n⌊⌋\sum\limits_{i=1}^{n}\left\lfloor \right\rfloor

知识关联

2 反向链接 · 1 提及笔记
局部关系图谱 悬停高亮 · 点击跳转