莫比乌斯反演学习笔记

Posted by Panda2134's Blog on March 12, 2018

莫比乌斯函数

我们定义

为什么这么定义?为了满足性质:

下面我们来证明上式.

当 $n = 1$ 时显然成立.

当 $n \ge 2$ 时,不妨设 $n = \prod_{i=1}^k p_i^{\alpha_i}$. $n$ 的恰含有 $r$ 个互异质因数的因子有$\binom{k}{r}$ 个.当它含有奇数个互异质因子时, 对答案贡献为 $-1$ , 含偶数个互异质因子时贡献为 $1$ .于是总的贡献为:

得证.

从上面的证明过程可以看出, 其实莫比乌斯函数就是在模拟容斥原理, 不过容斥的对象是唯一分解式中的指数罢了. 把不同的质因数看成盒子, 指数看成球, 就转为了经典的球-盒模型.

莫比乌斯反演

形式1:枚举约数

证明:

⇒:

⇐:

得证.

形式2:枚举倍数

这个形式比较常用.

我们不妨假设 $n, d \le N$ . 则:

这个比较难证明……想了好久……

证明:

⇒:

⇐:

得证.

一点重要的结论

证明1:利用法里级数
这是《具体数学》的证明方法。名字很玄乎,其实很直观。

我们考察以 $n$ 为底的所有真分数和1一起组成的集合。不妨假设 $n=12$ . 则这些分数是:

化简后就变成了:

按照分母分个组:

分母里面出现了 $n$ 的每个约数 $d$ . 对于每个约数 $d$ 对应的分组,分子上出现了 $\varphi(d)$ 个小于等于 $d$ 且与之互质的数。总共又有 $n$ 个分数。也就是说所有约数的 $\varphi(n)$ 之和就是 $n$ . 写成式子就是上式。得证。

证明2:利用 $\mu$ 函数的性质,构造出 $\mu(n)$ ,再使用莫比乌斯反演消去(%Anoxiacxy)

QED.

例题

一点感想:做数论题目一定要等忘了题解再做一次!这样才能看出你真正掌握没有!

BZOJ2440 完全平方数

求小于等于 $n$ 的无平方因子数个数。双倍经验:vijos天真的因数分解。

这个题一开始是看的PoPoQQQ的PPT,当时觉得很简单。今天看到那个双倍经验题,想了好久,甚至想到了杜教筛,却没想到更简单的方法……然而并不会杜教筛……

下面是一种利用容斥的方法:

答案= $n$ $-$ $1$个质数平方倍数的数目 $+$ $2$个不同质数乘积的平方倍数的数目 $-$ $3$个不同质数乘积平方倍数的数目 ……

要求“不同质数”,是为了避免重复统计。(“倍数”可以增加乘积中质因数的指数)有相同质因数的数字对答案贡献为0,这也与 $\mu$ 函数对应。

这个式子和莫比乌斯函数定义的容斥含义是一样的!!!即 $\mu(n) = (-1)^k,\text{当} n= p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ 。

奇数个互异质数为负,偶数个互异质数为正,质因子不互异贡献为0.是莫比乌斯函数作为容斥系数的要点。

$\Rightarrow \text{ans} = \sum_{d=1}^{\sqrt{n}} \mu(d) \left\lfloor\frac{n}{d^2}\right\rfloor$ . 可以整除分块求出。复杂度为 $O(n^{1/4})$ (不知道是不是算错了= =)

BZOJ2301 [HAOI2011]Problem b

莫比乌斯反演+数论分块,达到单组询问 $O(\sqrt{n})$ 的复杂度。

BZOJ3529 [SDOI2014] 数表

多组数据,直接类似求 $\sum_{i=1}^n\sum_{j=1}^m[\gcd(i, j) = d]$ 的暴力整除分块显然用不了。

考虑化式子,化成整除分块的量与数据无关的形式。

先考虑没有 $a$ 的限制怎么做。设 $n \le m$ ,如果 $n > m$ 将二者交换即可。

注意灵活地在枚举所有约数和所有倍数之间转换。

设 $\gamma = \sigma * \mu$,我们可以筛出 $\sigma, \mu$ 后通过枚举倍数来在 $O(n \log n)$ 的复杂度内求出 $\gamma$ 函数。

于是上式$:= \sum_{d=1}^n \left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor \gamma(d) $。

当有了 $a$ 的限制后,只有 $\sigma(k) \le a$ 的对答案有贡献。把询问离线,并按照 $a$ 排序,每次加入一部分 $\gamma(n)$ 的函数值,并求出前缀和——这可以用树状数组实现。每次对于一个 $\sigma(k)$ 枚举它的倍数,然后加入树状数组。


参考链接:

强烈推荐: