整除分块

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

$$\sum _{i=1}^{n}f\left(\lfloor \frac{n}{i}\rfloor \right)$$

这类涉及到 整除 或 取整 的求和问题,其核心思想是:对于固定的$n$,$\lfloor \frac{n}{i}\rfloor$的值在一定区间内是相同的,我们可以将这些 $i$ 连续区间优化为一次处理

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

$$k=\lfloor \frac{n}{i}\rfloor$$

当$i$增大时, $\frac{n}{i}$ 单调递减,故$k$是单调不增的

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

现在我们来求这个区间

$$\{\begin{array}{l}k=\lfloor \frac{n}{i}\rfloor \\ ⟺k\le \frac{n}{i}<k+1\\ ⟺\frac{n}{k+1}<i\le \frac{n}{k}\end{array}$$

因此:

$$L=\lfloor \frac{n}{k+1}\rfloor +1R=\lfloor \frac{n}{k}\rfloor$$

在遍历的时候我们更倾向于使用 $R$

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

遍历方法

整除分块的标准做法是:

从小到大遍历 $i$ ,一次跳过所有 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
}
 

Tip

注意整除分块中每一个循环都是一段区间的内容,所以不要忘记处理完成后将结果乘上区间长度r - l + 1

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

Solution1

void solve()
{
    i64 n;
    cin >> n;
    i64 ans = 0;
    // 注意for中 l 应该是 跳入到下一个块中
    for (i64 l = 1, r; l <= n; l = r + 1) {
        // 当前一个区间的整除数
        i64 k = n / l;
        // 计算块右边界
        r = n / k;
        // 计算结果(不要忘记块长)
        ans += k * (r - l + 1);
    }
    cout << ans << endl;
}

指向原始笔记的链接

另外一种形式的分块

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

$$\sum _{i=1}^n\lfloor \rfloor$$