整除-数论分块


前言

学习完莫比乌斯反演之后,Caicz 信心满满的打开一道例题,推出例如这样的式子
$$
\sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor(\sum_{k|T,k\in prime}\mu(\frac{T}{k}))
$$
之后,对于每组询问都这样做一遍果断T飞,于是果断点开题解,然后发现了多组求解的科技整除分块

整除分块

一般来说,我们会用到整除分块的形式大概长这样:
$$
\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor
$$
显然的,我们可以 $O(n)$ 快速计算这个式子。但是,有时候在多组询问下, $O(n)$ 解决每组询问也许并不能解决,于是我们就可以通过整除分块 $O(\sqrt{n})$完成每组询问

设 $f(x)=\lfloor\frac{n}{x}\rfloor$ ,则对于 $f(x)$ 我们容易发现它的值是连续且逐步递增的;简单来说即是呈块状分布。同时,我们通过打表等玄学方法可以得到每个块的最后一个数的位置即为 $\large{\frac{n}{\lfloor\frac{n}{i}\rfloor}}$ ,得出结论之后,我们就可以简单的 $O(\sqrt{n})$处理了

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

后记

整除分块单独来说并不难,但是有时候我们推出来的式子还会含有其他的函数,此时我们就需要对这些函数求一个前缀和

当然,在一些难度较高的题目里面,我们甚至难以接受 $O(n)$ 预处理前缀和,这时我们就需要运用杜教筛

参考博客

https://www.cnblogs.com/peng-ym/p/8661118.html


文章作者: Caicz
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Caicz !
评论
  目录