数论分块

数论分块

part 1 数论分块是什么

一道例题引入uva H(n)
题目大意是给定一个n,求\(\sum^{n}_{i=1}\lfloor\frac{n}{i}\rfloor\)
如果不能用\(O(n)\)的时间复杂度来算，能用什么办法？

数论分块！！！

在一个特定的区间内，\(\lfloor\frac{n}{i}\rfloor\)算出的数字是一样的。如下图颜色相同部分的区间

显然，我们可以把相同的\(\lfloor\frac{n}{i}\rfloor\)看成一个整体，用这个区间的右端-左端+1乘上它，就为这个区间的答案。

part 2 如何求左端右端

• 左端右端都是整数，左端就等于上一个右端+1。
• 由于\(\lfloor\frac{n}{l}\rfloor = \lfloor\frac{n}{r}\rfloor\leq\frac{n}{r}\)，所以\(r\leq\frac{n}{\lfloor\frac{n}{l}\rfloor}\)，即\(r=\frac{n}{\lfloor\frac{n}{l}\rfloor}\)