莫比乌斯反演 学习笔记

莫比乌斯反演

前置知识

数论分块

性质：对于前\(\sqrt n\)个数，分别在后面可以找到一个对应的、最大的数，令它们相乘所得的积不超过\(n\)，而对于后面的数，因为它们\(> \sqrt n\)，所以和它们所乘不超过\(n\)的数一定\(< \sqrt n\)
处理问题时，我们可以依照这种性质，只枚举\(2\sqrt n\)种不同的商，就可以完成题目，将复杂度从\(O(n)\)降低到\(O(\sqrt n)\) (较小数字极端条件下会退化成\(O(n)\)，但既然都是较小数字了，也不用在意)
经典实用场景：
Q1: P1403 [AHOI2005] 约数研究
形式化题意:请求出从1到n的所有约数个数之和
(暂停3秒，请大家想一想怎么解答，先不要看解答)
Ans1：
我们可以使用数论分块的性质
对于第一个\(i\)满足\(n/i=d\)，我们可以求得最大的\(j=n/d\)满足\(j*d \le n\)，所以\(i\)到\(j\)的数在\(n\)的范围内拥有\(d\)个倍数
以此类推，我们可以找到每一个数在1到\(n\)范围内有多少个倍数，自然也就找到了约数之和。复杂度\(O(2\sqrt n)\)

Q2：P2261 [CQOI2007] 余数求和
形式化题意：给出正整数\(n, k\)，求出\(i\)从1到\(n\)中每个\(k\mod i\)的和
(暂停3秒，请大家想一想怎么解答，先不要看解答)
Ans2:
我们可以将这个式子变成\(n*k- \sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor *i\)
对于前面的\(n*k\)，这很好算
对于后面的式子，运用整除分块的思想，我们可以得到\(2 * \sqrt min(n, k)\)块不同的\(\lfloor \frac{k}{i} \rfloor\)。因此，我们只需要对于每一段\(i \le x \le j\)中的所有x求和即可，即\((i+j) * (j-i+1) / 2\)，再乘上前面得到的\(\lfloor \frac{k}{i} \rfloor\)，我们就得到了答案
时间复杂度\(2 * \sqrt min(n, k)\)

Q3：P3935 Calculating
形式化题意：求从\(l\)到\(r\)的所有约数个数和
和上面的题一模一样，不多赘述，有兴趣的OIER们可以去做一下

Q4: P2424 约数和
形式化题意：求从\(x\)到\(y\)中所有约数和的和
和上面的题差不多，不多赘述，由兴趣的OIER们可以去做一下

不再前置的知识

莫比乌斯函数

对于一个莫比乌斯函数，我们有以下定义：

莫比乌斯函数 \(\mu(n)\) 的定义如下：

\[\mu(n) = \begin{cases} 1, & n = 1, \\[4pt] 0, & n \text{ 能被大于 } 1 \text{ 的平方数整除}, \\[4pt] (-1)^k, & n \text{ 是 } k \text{ 个不同素数的乘积}. \end{cases} \]

具体地，设正整数 \(n\) 的素因数分解为：

\[n = \prod_{i=1}^{k} p_i^{e_i}, \]

其中 \(p_i\) 是素数，\(e_i\) 是正整数。则三种情形分别对应：

• \(\mu(1) = 1\)；
• 若存在某个 \(i\) 使得 \(e_i > 1\)（即 \(n\) 有素因子的指数大于 1），则 \(\mu(n) = 0\)；
• 否则，对所有 \(i\) 都有 \(e_i = 1\)（即 \(n\) 无平方因子），则 \(\mu(n) = (-1)^k\)，其中 \(k\) 就是 \(n\) 的不同素因子的个数。

模版：用线性筛求莫比乌斯函数
思路如下：
对于\(1\)，由上可知其 \(\mu(1) = 1\)
对于任意一个质数，由上可知其 \(\mu(i) = -1\)
对于剩下的数，我们分为两类：当你目前枚举的质因子\(p\)不能够整除你目前的数\(i\)时，那么由上它的 \(\mu(p*i) = -\mu(i)\)；当你目前枚举的质因子\(p\)能够整除你目前的数\(i\)时，那么由上它的 \(\mu(p*i) = 0\)

性质1：
对于\(\sum_{i=1}^{n} \mu(i)\)，其总和等于\([n=1]\)("[]"为Iverson括号，括号内条件满足则是1，不满足则是0)
证明1：
作者目前还不会证，会证了再补

狄利克雷卷积

作者也不知道是什么呢~

性质应用1：\([\,i \perp j\,] = [\,\gcd(i,j) = 1\,] = \sum_{d \mid \gcd(i,j)} \mu(d) = \sum_{d} [\,d \mid i\,][\,d \mid j\,] \mu(d).\)
性质证明1：
作者目前还不会证，会证了再补

莫比乌斯反演

主要结论：设\(f(n), g(n)\)是两个数论函数，那么有\(f(n) = \sum_{d \mid n} g(d) \quad \Longleftrightarrow \quad g(n) = \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) f(d).\)

常见题型：对于gcd问题中，若有\(gcd(i, j) = k, 且a \le i \le b，c \le j \le d\)，或其变体(如倍数等)，通常可以使用莫比乌斯反演

Q1：[]