引入
在求解
\[\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor \]时,我们可以很容易的想到用 \(O(n)\) 求解。
但如果 $n \leq 10^9 $甚至往上的时候，我们这么做就会超时，我们需要一种更高效的方法来计算，整除分块。
原理
比较容易发现，在 \(i\) 取某些值的时候，\(\lfloor \frac{n}{i} \rfloor\) 的值就是相同的，我们就把他们合并起来，找到 \(l\) 和 \(r\) ,一起计算，减少计算次数。
时间复杂度
当 \(i \leq \sqrt n\) 时显然 \(\lfloor \frac{n}{i} \rfloor\) 的取值只有 \(\sqrt n\) 种可能；而当 \(i > \sqrt n\) 时有 \(\frac{n}{i} < \sqrt n\) ，所以 \(\lfloor \frac{n}{i} \rfloor\) 的取值同样只有 \(\sqrt n\) 种可能，也就是说 \(\lfloor \frac{n}{i} \rfloor\) 的取值只有 \(2\sqrt n\) 种可能，对于同样的取值只用计算一次，总的时间复杂度也就是 \(Θ(\sqrt n)\)。
具体实现
首先我们设我们的左端点是 \(l\) ,那么 \(\lfloor \frac{n}{l} \rfloor = k\) ,我们假设右端点 \(r=l+d\) , 使得 \(\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{l+d} \rfloor = k\) 。展开得到 \(n = kl+p\) 和 \(n=k(l+d)+p'\) \((1 \leq p < l)\)。
$ \therefore kl+p = k(l+d) + p'$
$ \therefore p'=p-kd$
$ \because p' \ge 0 \ $
$ \therefore p \ge kd$
$ \therefore d \leq \frac{p}{k} $
$ \because d \in N^* \ \ \ $
$ \therefore d \leq \lfloor \frac{p}{k} \rfloor$
$ \because p = n \ mod \ l = n-l\lfloor \frac{n}{l} \rfloor \ \ \ $
$ \therefore r = l + d_{max}$
$ \ \ \ \ \ \ \ = l + \lfloor \frac{p}{k} \rfloor$
$ \ \ \ \ \ \ \ = l + \lfloor \frac{n-l\lfloor \frac{n}{l} \rfloor}{\lfloor \frac{n}{l} \rfloor} \rfloor$
$ \ \ \ \ \ \ \ = l + \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor - l$
$ \ \ \ \ \ \ \ = \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$
\(QED\)
所以说，对于每一个左端点为 \(l\) 的块，他的右端点就是 $ \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ 。
所以，当我们求
\[\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor \]的时候，\(l\) 从 \(1\) 开始枚举，每次右端点 \(r\) 取
$ min(n,\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor)$ ，将整块答案累加，然后令 \(l=r+1\)，直到等于 \(n\) 的时候停止。
练习
\(P3935\) \(P2261\)
标签：lfloor,frac,分块,sqrt,leq,rfloor,整除,therefore From： https://www.cnblogs.com/bloodstalk/p/17432777.html