前言
最近在学莫比乌斯反演, 然而只看懂了莫比乌斯函数, 然后反演看着一脸懵逼, 最后只看懂了数论分块里面的一个分支内容(也是莫比乌斯反演的前置姿势), 整除分块
于是写一篇博文记录一下整除分块
整除分块
整除分块是用于快速处理形似
\[ \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...\)
来源: https://www.cnblogs.com/henry-1202/p/10121854.html