整除分块
我们在这里主要聊的是 整除分块 ,这是求解形如
这类涉及到 整除 或 取整 的求和问题,其核心思想是:对于固定的,的值在一定区间内是相同的,我们可以将这些 连续区间优化为一次处理
对一个固定的 n ,我们考虑其表达式
当增大时, 单调递减,故是单调不增的
对于某个确定的,所有满足的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
}
cpp一个例子,可以看下面计算约数计数和
Solution1
另外一种形式的分块
这种形式的分块主要是以下类型
知识关联
2 反向链接 · 1 提及笔记
局部关系图谱
悬停高亮 · 点击跳转