整数分块

发布于 2020-05-10 | 分类于数学 | 2分钟 | 348字数 | 浏览量：

~~现在来补一下小知识~~

\sum_{i=1}^{n}\frac{n}{i}

求上式。

考虑先打个表，方便理解。令 $n=10$ ，则：

i	1	2	3	4	5	6	7	8	9	10
$\frac{n}{i}$	10	5	3	2	2	1	1	1	1	1

我们可以发现对于 $i$ 递增时， $\frac{n}{i}$ 呈不上升，可以直接数学证明。

那么我们对于 $\frac{n}{i}$ 相同的连续区间作为一个块，将序列进行分块。

令 $[l,r]$ 是一个块，那么我们可以发现对于 $i\in[l,r]$ ，都有 $\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{l}\rfloor$ 。

现在考虑如何使用这个性质把分块进行扩展。

此时发现当 $i=r$ 时， $\frac{n}{i}=\lfloor\frac{n}{i}\rfloor$ ，我们知道 $l$ 的代数值后，则 $r=\frac{n}{\lfloor\frac{n}{l}\rfloor}$ 。

所以，初始化 $l=1$ ，再把 $r$ 进行扩展，发现块与块之间的转移 $l=r+1$ 。

时间复杂度从 $O(n)$ 简化到了 $O(\sqrt{n})$ 。

放一份模板题的核心代码：（洛谷-P2261 [CQOI2007]余数求和）

for(lint l=1,r=1;l<=n;(l=r)++)
{
	r=((k/l) ? min(k/(k/l),n) : n);
	ans-=((l+r)*(r-l+1)/2)*(k/l);
}

感谢您的支持，我会继续努力的!