莫比乌斯反演


前言

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

莫比乌斯函数

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

定义

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

性质

  1. 对于任意正整数 $n$ ,满足 $\sum_{d|n}\mu(d)=[n=1]$ ,即只有 $n=1$ 是返回值为 $1$ ,否则为 $0$
  2. 对于任意正整数 $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}
$$
至此,莫比乌斯反演的基本内容就结束了,接下来有一些例题

例题

YY的gcd
[SDOI2015]约数个数
[国家集训队]Crash的数字表格

后记

如果你要想完成这些例题,你还需要掌握整除分块

参考博客

https://www.cnblogs.com/peng-ym/p/8647856.html


文章作者: Caicz
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Caicz !
评论
  目录