莫比乌斯反演整理

UPD:我就是个菜鸡QAQ写的这些东西哎……太弱的时候什么都敢乱写……神犇看到就当开笑话嘛QAQ……求不喷

莫比乌斯反演通常是利用莫比乌斯函数来简化一类逆向求函数的问题。
设\(F(n)\)与\(f(n)\)是定义在自然数集合上的两个数论函数,并且满足条件$$
F(n) = \sum_{d|n}f(d)
$$或者$$
F(n) = \sum_{n|d}f(d)
$$已知的\(F(n)\),求\(f(n)\)的表达式。

观察\(F(n)\)式:\(F(n)\)被\(F(xn)(x > 1)\)所包含。所以,只需类似解多元一次方程一样,通过抵消系数的方法(容斥)就可以逐个求出\(f(n)\)。
但是这样太慢了!于是我们想加速这个过程。
我们希望,存在一个函数,使得\(F(n)\)可以直接被表示出来。

这里先给出结论,有莫比乌斯反演公式$$
f(n) = \sum_{d|n} \mu(d) F(\frac nd)
$$或者$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d)
$$其中,莫比乌斯函数\( \mu(n) \)即是我们所要的容斥函数,\( \mu(n) \)定义为$$ \mu(n)=
\begin{cases}
1 \ \quad \quad d = 1 \\
(-1)^k \ n = p_1 p_2 \ldots p_k ,p_i为互异的质数\\
0 \ \quad \quad else \\
\end{cases}
$$同时,\( \mu(n) \)还有几个性质:
(1)\( \mu(n) \)是积性函数,即对于互质的正整数\(a,b\)有$$ \mu(ab) = \mu(a) \mu(b) $$(2)对于任意正整数\(n\)有$$\sum_{d|n} \mu(d) = [n = 1]$$(3)对于任意正整数\(n\)有$$\sum_{d|n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$这些性质都是可以证明的,详见最后。
利用莫比乌斯函数的第二个性质,可以证明第一个莫比乌斯反演公式:$$
\begin{align*}
f(n) &= \sum_{d’|n}[d’=1]f(\frac N{d’}) \\
&= \sum_{d’|n}f(\frac n{d’}) \sum_{d|d’} \mu(d) \\
&= \sum_{d|n} \mu(d) \sum_{k | \frac n d} f(\frac n {dk}) \\
&= \sum_{d|n} \mu(d) F(\frac n d)
\end{align*}
$$类似的可以证明第二个公式。
当然,因为我们用到了函数的性质,这给人一种钦定的感觉。所以我找到一篇文章完整讲了莫比乌斯函数的朴素证明和构造性证明: http://blog.csdn.net/danliwoo/article/details/51866867

求莫比乌斯函数的话,可以利用莫比乌斯函数的定义在\(O(\sqrt{n})\)的时间内通过分解质因数的方法得到任意\( \mu(n) \)的值:

也可以在\(O(n)\)的时间内通过线性筛法在筛素数的同时求得\( \mu(1 \ldots n) \)的值:

首先先看一个并不需要莫比乌斯反演的问题,求$$
\sum_{a=1}^N \sum_{b=1}^N [\gcd(a,b) = 1], \ N \leq 10^7
$$我们发现这个式子后半部分和欧拉函数\( \varphi(n) \)的定义是类似的。因为数对\( (x,y) \)是有序的,所以当\( x \neq y \)时需要算两遍,注意到\( \gcd(x, x) = 1\)的充要条件是\( x = 1\),所以答案就是$$
\sum_{d = 1}^{N} 2\varphi(\lfloor \frac nd \rfloor) \ – 1
$$
那么再来看一个问题,求$$
\sum_{a=1}^N \sum_{b=1}^M [\gcd(a,b) = 1], \ N \leq \ M \leq 10^7
$$对于这道题就不能只用欧拉函数解决了,需要用莫比乌斯反演来解决。我们考虑定义\(F(n)\)与\(f(n)\),然后利用莫比乌斯反演公式来进行转换。
我们发现这样定义\(F(n)\)与\(f(n)\)比较友好:$$
f(n) = \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=n] \\
F(n) = \sum_{n|d} \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=d]
$$其中,\(f(1)\)就是我们要求的答案,\(F(d)\)就是统计所有\(a|d\)且\(b|d\)的合法的数对\( (a,b) \)的个数。那么就有$$
F(n) = \lfloor \frac Nn \rfloor \lfloor \frac Mn \rfloor
$$于是我们代入前面提到的第二种莫比乌斯反演公式得到$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d) = \sum_{n|d} \mu(\frac dn) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$此时我们令\(n = 1\),有$$
f(1) = \sum_{d = 1}^N \mu(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$这个式子就是答案。

如果通过质因数的方法求\(\mu(1 \ldots N)\),时间复杂度为\(O(N \sqrt N)\),过不了;
如果线性筛预处理\(\mu(1 \ldots N)\),预处理\(O(N)\),查询\(O(N)\),已经能过了;

其实还有更快的查询方法。事实上\(\lfloor \frac Nd \rfloor \)的取值个数非常小(易证一定不大于\(2 \sqrt N \)),并且在\(d\)递增时,\(\lfloor \frac Nd \rfloor \)均是单调不升并且连续的,这意味着,\( \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor \)的取值对总数是\( O(\sqrt M) \)的!
所以我们可以在\(O(\sqrt M) \)的时间内完成一次查询,实现如下:

差不多就这样辣……

用类似的方法,推出和式,有时再加一点其他的优化(比如杜教筛),就是莫比乌斯反演的套路了。
(然而不是莫比乌斯模板题我还是不会做QAQ)

这里有一个Po姐的PPT,写的非常棒,反正能看懂很多东西吧……
PoPoQQQ的良心PPT

2 comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注

ˆ Back To Top