问题引入
求 \(\sum\limits_{i=1}^N\lfloor\dfrac{N}{i}\rfloor,N\le 10^{12}\)
整除分块
我们这道题暴力枚举显然不行。
考虑向下取整的性质：向下取整得到的数一定是 \(N\) 的因子。
我们不难发现，一个整数 \(N\) 的因子最多有 \(2\sqrt{N}\) 个。
证明：很简单，我们设 \(xy=N(x\le y)\)，则 \(x\le\sqrt{N}\)。那么 \(x\) 的个数最多为 \(\sqrt{N}\) 个，而 \(xy\) 一定是成对出现的，所以 \(N\) 的因子最多 \(2\sqrt{N}\)。
那么我们考虑如何利用这个 \(2\sqrt{N}\) 来解决。
即，我们记 \(k=\dfrac{N}{i}[i\equiv 0 \pmod N],k'=\lfloor\dfrac{N}{i'}\rfloor\)，令 \(k=k'\)。
我们考虑此时的 \(i'_{\max}\) 是多少。
先说结论：\(\biggl\lfloor\dfrac{N}{\lfloor\frac{N}{i}\rfloor}\biggl\rfloor\)。
证明：
已知 \(k=\dfrac{N}{i}[i\equiv 0 \pmod N]\) 可以有 \(i\times k+p=N(0\le p<i)\)，对于 \(\lfloor\dfrac{N}{i+d}\rfloor,i'=i+d\) 有 \((i+d)\times k+p'=N(0\le p'<i)\)。
则 \(p'=p-kd\)，所以 \(d\le\lfloor\dfrac{p}{k}\rfloor\)
好了，现在我们只需要用一个双指针 \(l,r\) 来维护一下每一个因子就行了，时间复杂度 \(O(\sqrt{N})\)。