整除分块

问题：求 $\sum_{i=1}^N \lfloor \frac{N}{i}\rfloor,N\leq10^{14}$。

怎么办呢？

暴力？

肯定会 TLE。

这个时候就要请出我们的整除分块了，时间复杂度为 $O \sqrt{N}$。

很明显，在 C++ 语言中，除法都是向下取整的，所以在一段整数区间内，除以同一个数得出来的结果将会成一段一段表示。

这里有两个定理：

1. $\lfloor\frac{N}{i}\rfloor$ 最多只有 $2\sqrt{N}$ 种取值。

   证明：对于 $i\leq\sqrt{N}$，很明显，$i$ 只有 $\sqrt{N}$ 种选择，对于 $i>\sqrt{N}$，$\frac{N}{i}<\sqrt{N}$，也只有 $\sqrt{N}$ 种选择，所以总共也就 $2\sqrt{N}$ 种取值。

2. 设 $\large \lfloor \frac N{i'} \rfloor$ 与 $\large \lfloor \frac Ni \rfloor$ 相等，则 $i'$ 的最大值为 $\large \left \lfloor \frac N{\left \lfloor \frac Ni \right \rfloor } \right \rfloor$

   证明：

   设 $\large{ \lfloor \frac Ni \rfloor}=k$，于是可以写成 $ki+p=N,1\le p<i$ 的形式，若 $\large{\lfloor \frac N{i+d} \rfloor}=k$，于是有 $k(i+d)+p'=N$，可以得到 $p'=p-kd$ ，则 $d$ 能取的最大值为 $\large \lfloor \frac pk \rfloor$ ，于是：

   $$i'=i+d_{max}=i+\lfloor \frac{p}{k}\rfloor=i+\lfloor \frac{N\bmod i}{\lfloor \frac{N}{i}\rfloor}\rfloor=i+\lfloor \frac{N-\lfloor\frac{N}{i}\rfloor i}{\lfloor \frac{N}{i}\rfloor}\rfloor=\lfloor i+\frac{N-\lfloor \frac{N}{i} \rfloor i}{\lfloor \frac{N}{i} \rfloor}\rfloor=\lfloor \frac{\lfloor \frac{N}{i}\rfloor i}{\lfloor \frac{N}{i}\rfloor}+\frac{N-\lfloor \frac{N}{i}\rfloor i}{\lfloor \frac{N}{i}\rfloor}\rfloor=\large \left \lfloor \frac N{\left \lfloor \frac Ni \right \rfloor } \right \rfloor$$

   然后，设两个指针 $L$ 和 $R$ ，$L$ 的初始值为 $1$ ，每次令 $\large R=\left \lfloor \frac N{\lfloor \frac NL \rfloor} \right \rfloor$ ，将 $\large (R-L+1)\cdot \lfloor \frac NL \rfloor$ 累加至答案中 ，再令 $L=R+1$，问题解决。