莫比乌斯反演

前言

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

莫比乌斯函数

我们称莫比乌斯函数为 $\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