【数学】整除分块

目前只在莫比乌斯反演里面看见过。

用于求$$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$形式的式子。

直觉告诉我们，$$\left\lfloor\frac{n}{i}\right\rfloor$$的很多值都一个样，最后一个是$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$$。所以直接把这一整块相加就好，时间复杂度$$O(\sqrt{n})$$。

简单证明

$$ \left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\ $$

$$ \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i $$

$$ i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor\ $$

代码

for(int le=1, ri; le <= n; le = ri + 1) {
    ri = n / ( n / le);
    ans += (ri - le + 1) * (n / le);
}