数论分块

ACM

数论分块是简单的结论,这里相较于OIWiki上的叙述补充点东西.

数论分块

结论:对于区间lr,满足 $\lfloor\frac nx\rfloor$ 的最大区间边界是

代码:

1
2
3
4
for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    //do something
}

时间复杂度是 $O(\sqrt n)$ .

多次分块

有的时候要处理诸如 $\lfloor\frac nx\rfloor\lfloor\frac mx\rfloor$ 的两个都需要分块的式子.这个时候代码怎么写?很简单.如下:

1
2
3
4
for(int l=1,r;l<=min(n,m);l=r+1){
    r=min(n/(n/l),m/(m/l));
    //do something
}

这其实就是一段一段的划分更细了.其时间复杂度是 $O(\sqrt n+\sqrt m)$ .

注意:以下代码是相对错误的示例,太难调了

1
2
3
4
5
6
7
for(int l1=1,r1,l1<=min(n,m);l1=r1+1){
    r1=n/(n/l1);
    for(int l2=l1,r2,l2<=r1;l2=r2+1){
        r2=m/(m/l1);//其实这里错了,因为r2有可能越界
        //do something
    }
}