数论分块

2018/12/14 23:40
阅读数 37

前言

最近在学莫比乌斯反演,然而只看懂了莫比乌斯函数,然后反演看着一脸懵逼,最后只看懂了数论分块里面的一个分支内容(也是莫比乌斯反演的前置姿势),整除分块。 于是写一篇博文记录一下整除分块 也称数论分块 数论分块是莫比乌斯反演一个很重要的的前置知识(基本都要用到这个玩意) 已经看完莫反啦,打算写一篇博客来记录一下莫反。

整除分块

整除分块是用于快速处理形似 $$ \sum_{i=1}^{n}{\lfloor \frac{n}{i} \rfloor} $$ 的式子的方法 很显然,这个可以$O(n)$得到答案。但是,在某些题目中,毒瘤出题人将数据加强到了$10^{10}$以上,这个时候我们就无法通过$O(n)$的解法来得到答案了。我们需要一个$O(\sqrt{n})$的更为优秀的解法 首先观察这个式子,找几个特殊值代入 n=5时,sum=5+2+1+1+1 可以发现的是:(这里给的例子并不明显,其实应该找一个大的n来代入才直观,读者可以自行尝试) 对于单一的$\lfloor \frac{n}{i} \rfloor$,某些地方的值是相同的,并且呈块状分布 通过进一步的探求规律与推理以及打表与瞎猜,我们可以惊喜的发现一个规律,这些块状分布的值是有规律的 对于一个块,假设它的起始位置的下标为l,那么可以得到的是,它的结束位置的下标为$\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor} \rfloor$ 如果实在看的有点懵逼,可以继续采用代入特殊值的方法,验证一下上方的规律,用程序表现出来即为

//l为块的左端点,r为块的右端点
r=n/(n/l)

在实际应用中,需要注意的就是除法除0的问题(一般都需要特判一下n/l) 程序实现也十分简单

int ans = 0;
for(int l = 1, r = 0; l <= n; l++) {
    r = n / (n / l);
    // do something
}

实际应用

例题:BZOJ1257: [CQOI2007]余数之和

这题其实就是求 $$ \sum_{i=1}^{n}{k\space mod\space i} $$ 这题和整除分块又有什么关系呢? mod没有什么特殊的性质,所以我们将它展开来,就变成了 $$ \sum_{i=1}^{n}{k\space-\lfloor \frac{k}{i} \rfloor*i} $$ 于是我们就看到了一个熟悉的形式,也就是整除分块的一般形式

再次改一下这个式子 $$ nk-\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloori} $$ 那么$\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloor*i}$和普通的整除分块有什么差别呢?

其实就是多了一个i

确实,就是多了一个i而已,只需要简单的化简一下,这个i就对我们的处理没有什么影响了

因为我们知道,对于一个整除分块$\sum_{i=l}^{r}{\lfloor\frac{k}{i}\rfloor}$,其中的每个值都是相同的,于是我们可以设$T=\lfloor\frac{k}{i}\rfloor$

式子就化为了 $$ \sum_{i=l}^{r}Ti \ =\sum_{i=l}^{r}{T}\sum_{i=l}^{r}i $$ 也就是说,其实这个式子前半段是一个整除分块,后半段是一个首项为l,公差为1的等差数列

至此,我们就圆满的解决了这个问题,可以在$O(\sqrt{n})$的时间内解决本题

这是整除分块中最基础的应用,就是单纯的利用整除分块来加速递推的实现,而实际上,整除分块更多的与其他函数结合在一起来使用,优化问题的求解

整除分块与积性函数

说到积性函数,就不得不讲到两个广为人知的函数$\phi,\mu$,这是我们最熟悉的积性函数~~(其实我也只知道这两个)~~ 积性函数有一个很好用的性质(设$f(i)$为一个积性函数): $$ f(ij)=f(i)f(j) $$ 这里的$f(i)$其实是一个完全积性函数。($\phi$就不是一个完全积性函数:$\phi(ij)=\phi(i)\phi(j)$当且仅当i,j互质才成立) 好了,讲完积性函数的这个性质后我们步入正题,整除分块与积性函数的联系 很多时候,我们推出来整除分块的式子不是很裸的,常与其他函数结合(通常是积性函数,通常为$\mu$或$\phi$) 这个时候如何统计答案呢? 比如: $$ \sum_{i=1}^{n}{\mu(i)*\lfloor \frac{n}{i}\rfloor} $$ 积性函数的性质! 因为积性函数这个很好用的性质,所以我们可以直接对前半段的莫比乌斯函数维护一个前缀和,再利用整除分块处理式子的后半段,处理答案的时候,把两段相乘即可

例题

BZOJ2956: 模积和

展开阅读全文
mu
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部