首页 > 技术文章 > 整除分块

ZJNU-huyh 2020-07-24 18:45 原文

整除分块的定义:例如我们求1~n的n/i的总和,如果遍历,极其容易超时,通过打表,我们发现有很多的(n/l)~(n/r)的值是重复的,整数分块就是为了寻找这样的区间。

例如:

所以我们可以将一个完全暴力的问题,转化成一个不超过O(2sqrt(n))时间复杂度的问题。

代码:

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

Ps:l和r为n/i取下整后,i的最小值和最大值。


 正确性的证明:

推荐阅读