整除分块学习笔记

## 前置知识 - ~~莫比乌斯反演~~ ~~上面的标题应该改为后置知识~~ ## 前言 最近在嗑莫比乌斯函数时嗑到了这个知识点，本质上是一个经常与莫比乌斯反演一起出现的小技巧，包括在很多莫比乌斯反演的题目中。 ## 算法过程 整除分块通常被用来处理类似下方的式子： $$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$ ### 暴力 首先我们可以暴力解决： ```cpp int ans = 0; for(int i = 1; i <= n; i++) { ans += n / i; } ``` $$N \leq 10^9$$ 然后就歇菜了 ### 规律 我们可以通过打表的方式来寻找$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$的规律 当$n=5,sum=5+2+1+1+1$ 当$n=9,sum=9+4+3+2+1+1+1+1+1$ 当$n=12,sum=12+6+4+3+2+2+1+1+1$ 可以看到有很多数是重复的，当$n$更大时，重复的数会更多。可以证明，这些数的数量是$O(\sqrt{n})$的。换句话说，我们可以将每一段连续且相同的数分开计算，实现$O(\sqrt{n})$的时间复杂度。 ### 实现 可以证明，对于一段相同且连续的数，若其左端点为$l$，则右端点为$\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ 即这一段$r-l+1$个数都为$\lfloor \frac{n}{l} \rfloor$，$l$到$r$的总和为$\lfloor \frac{n}{l} \rfloor * (r - l + 1)$ ```cpp for(int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (r - l + 1); } ``` ## 应用 ### 「CQOI2007」余数求和 这道题的关键是求$\sum_{i=1}^n i * \lfloor \frac{n}{i} \rfloor$ 在此题中，$l$到$r$的总和为$\sum_{i=l}^{r} i * \lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{l} \rfloor \sum_{i=l}^{r} i = \lfloor \frac{n}{l} \rfloor * \frac{(l + r)(r - l + 1)}{2}$ ```cpp for(int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (l + r) * (r - l + 1) / 2; } ``` ### 莫比乌斯反演 在莫比乌斯反演中，我们经常需要求$\sum_{i=1}^n \mu(i) * \lfloor \frac{n}{i} \rfloor$ 在同一段内的和为$\sum_{i=l}^{r} \mu(i) * \lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{l} \rfloor \sum_{i=l}^{r} \mu(i) = \lfloor \frac{n}{l} \rfloor (\sum_{i=1}^{r} \mu(i) - \sum_{i=1}^{l-1} \mu(i))$ 使用线性筛可以在$O(n)$的时间内预处理所有的$\sum_{i=1}^{k} \mu(i)$，整除分块复杂度为$O(\sqrt{n})$，总复杂度$O(n)$ ```cpp for(int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + mu[i]; } for(int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (sum[r] - sum[l - 1]); } ```