莫比乌斯反演

莫比乌斯反演数学

基础学习

发布日期: 2020-08-21

阅读次数:

前言

鸽了许久的数论从莫反开始了……

莫比乌斯函数

我们称莫比乌斯函数为 $\mu(d)$ ，它是一个积性函数，也是一个由容斥系数构成的函数

定义

$$
\mu(d)=\begin{cases}
1&(d=1)\\
(-1)^k&(d=p_1p_2p_3\cdots p_k)\\
0&otherwise
\end{cases}
$$

性质

对于任意正整数 $n$ ，满足 $\sum_{d|n}\mu(d)=[n=1]$ ，即只有 $n=1$ 是返回值为 $1$ ，否则为 $0$
对于任意正整数 $n$，满足 $\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$

求解

我们根据积性函数的性质，可以直接线筛出 $\mu(n)$

线筛代码:

inline void get_mu(int n)
{
    mu[1]=1;
    for(register int i=2;i<=n;++i)
    {
        if(!vis[i])
        {
            prim[++cnt]=i;
            mu[i]=-1;
        }
        for(register int j=1;j<=cnt&&prim[j]*i<=n;++j)
        {
            vis[prim[j]*i]=1;
            if(!(i%prim[j]))break;
            else mu[i*prim[j]]=-mu[i];
        }
    }
 }

~~好了，我们以及学会了莫比乌斯函数了，试试看，自己推出莫比乌斯反演吧~~

定理

$F(n)$ 和 $f(n)$ 是定义在非负整数集合上的两个函数，并且满足条件:
$$
F(n)=\sum_{d|n}f(d)
$$
那么存在结论:
$$
f(n)=\sum_{d|n}\mu(d)\cdot F(\frac{n}{d})
$$
这个定理就被称作莫比乌斯反演定理

当然莫比乌斯反演也存在另外一种形式的结论，即当
$$
F(n)=\sum_{n|d}f(d)
$$
存在结论
$$
f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot F(d)
$$

证明

一般来说，莫比乌斯反演的证明有两种方式，其中一种是通过定义来证明；另外一种则是利用狄利克雷卷积。这里只有第一种证明方法
$$
\begin{align}
&\sum_{d|n}\mu(d)F(\frac{n}{d})\\
=&\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i)\\
=&\sum_{i|{n}}f(i)\sum_{d|\frac{n}{i}}\mu(d)\\
=&f(n)
\end{align}
$$
至此，莫比乌斯反演的基本内容就结束了，接下来有一些例题