整除分块

约 270 个字 10 行代码 预计阅读时间 1 分钟

快速计算一些含有除法向下取整的式子，形如

$\sum\limits_{i=1}^nf(i)g(\left\lfloor\dfrac ni\right\rfloor)$

当可以 $O(1)$ 计算 $\sum\limits_{i=l}^r f(i)$，整除分块就可以 $O(\sqrt n)$ 计算上述式子的值

原理

前缀和,树状数组,分块求$\sum\limits_{i=l}^r f(i)$

$\left\lfloor\dfrac ni\right\rfloor$ 的值成一个块状分布（就是同样的值都聚集在连续的块中）

值 $\left\lfloor\dfrac ni\right\rfloor$ 所在的块的右端点为 $\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor$

原式计算就可以转化为以下代码

int block(int n)
{
    int res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        res+=(f[r]-f[l-1])*g[n/l];
    }
    return res;
}

例题

求$\sum\limits_{i=1}^n \lfloor\frac ni\rfloor$

多维整除分块

求含有 $\left\lfloor\dfrac {a_1}i\right\rfloor$、$\left\lfloor\dfrac {a_2}i\right\rfloor\cdots\left\lfloor\dfrac {a_n}i\right\rfloor$ 的式子时

整除分块右端点的表达式从一维的 $\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor$ 变为 $\min\limits_{j=1}^n{\left\lfloor\dfrac {a_j}{\left\lfloor\dfrac {a_j}i\right\rfloor}\right\rfloor}$，

即对于每一个块的右端点取最小的那个作为整体的右端点