数论分块之整除分块

· · 题解

前言

最近在学莫比乌斯反演，然而只看懂了莫比乌斯函数，然后反演看着一脸懵逼，最后只看懂了数论分块里面的一个分支内容（也是莫比乌斯反演的前置姿势），整除分块 于是写一篇博文记录一下整除分块

P.S. 同步于我的个人博客

整除分块

整除分块是用于快速处理形似\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}

于是我们就看到了一个熟悉的形式，也就是整除分块的一般形式

再次改一下这个式子

n*k-\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloor*i}

那么\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}T*i =T*\sum_{i=l}^{r}i

也就是说，其实这个式子前半段是一个整除分块，后半段是一个首项为l，公差为1的等差数列

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

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

整除分块与积性函数

说到积性函数，就不得不讲到两个广为人知的函数\phi,\mu，这是我们最熟悉的积性函数（其实我也只知道这两个）

积性函数有一个很好用的性质（设f(i)为一个积性函数）：

f(i*j)=f(i)*f(j)

这里的f(i)其实是一个完全积性函数。（\phi就不是一个完全积性函数：\phi(i*j)=\phi(i)*\phi(j)当且仅当i，j互质才成立）

好了，讲完积性函数的这个性质后我们步入正题，整除分块与积性函数的联系 很多时候，我们推出来整除分块的式子不是很裸的，常与其他函数结合（通常是积性函数，通常为\mu或\phi）

这个时候如何统计答案呢？

比如：

\sum_{i=1}^{n}{\mu(i)*\lfloor \frac{n}{i}\rfloor}

积性函数的性质！

因为积性函数这个很好用的性质，所以我们可以直接对前半段的莫比乌斯函数维护一个前缀和，再利用整除分块处理式子的后半段，处理答案的时候，把两段相乘即可 当然，整除分块能结合的函数肯定不止这么几个（但是由于博主太菜所以并不知道其他的函数与整除分块结合的方法）

To\ Be\ Continue...