学术：浅谈数论分块

这个式子有着很好的性质，他经常出现，也是我们正常 n / i 计算出来的值。最重要的是，他对很多 来说，是一样的。这让“组合数性质”发挥了作用：统计单个贡献，统计个数，批量计算。但是，凡事都要有理论基础：

复杂度证明

取 分成两段：

• ，此时 ，有最多根号级别的种类；
• ，此时 ，也只有最多根号级别的种类；

数论分块时间复杂度与块数有关，块内是可以批量统计的，所以为 。

两个性质

1. 相等的 i 一定在一个连续的区间内；
2. 块左端点为 时，右端点 = ；

第一个性质过分简单了，不做证明。

下面是第二个性质的证明：

证明

对于满足 的 ，有：

则有：

即有：

又 ，则 最大值为 。