问题：求 ∑i=1N⌊Ni⌋,N≤1014\sum_{i=1}^N \lfloor \frac{N}{i}\rfloor,N\leq10^{14}。

怎么办呢？

暴力？

肯定会 TLE。

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

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

这里有两个定理：

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

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

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

    证明：

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

    i′=i+dmax=i+⌊pk⌋=i+⌊N mod i⌊Ni⌋⌋=i+⌊N−⌊Ni⌋i⌊Ni⌋⌋=⌊i+N−⌊Ni⌋i⌊Ni⌋⌋=⌊⌊Ni⌋i⌊Ni⌋+N−⌊Ni⌋i⌊Ni⌋⌋=⌊N⌊Ni⌋⌋ 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

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