莫比乌斯反演

莫比乌斯函数如下 $\mu(d)= \begin{cases} 1 &\mbox{d=1}\\ (-1)^k &\mbox{$d=p_1p_2p_3...p_k,p_i$是互异素数}\\ 0 &\mbox{其余情况} \end{cases}$

于是有如下两条性质
$\sum_{d|n}^{}{\mu(d)=[n=1]}$
$\sum_{d|n}^{}{\frac {\mu(d)}{d}}={\frac {\phi(n)}{n}}$

第一个性质用组合数可以很方便得到

莫比乌斯反演如下
如果有
$f(n)=\sum_{d|n}^{}{g(d)}$ 那么
$g(n)=\sum_{d|n}^{}{\mu(d)\cdot f(\frac nd)}$

$\sum_{d|n}^{}{\mu(d)\cdot f(\frac nd)}=\sum_{d|n}^{}{\mu(d)\cdot \sum_{k| \frac nd}^{}g(k)}$

$=\sum_{d|n}^{}{\sum_{k| \frac nd}^{}{\mu(d) \cdot g(k)}}$

显然其实就是枚举$d\cdot k|n$

即$=\sum_{k|n}^{}{\sum_{d| \frac nk}^{}{\mu(d) \cdot g(k)}}$

由性质1可得该式$=g(n)$

(其实我每次都没构造函数,我直接推的2333…)
上一段线筛莫比乌斯函数代码
1
2
3
4
5
6
7
8
9
10
11
void get_mu(int n){
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i])mu[i]=-1,p[++cnt]=i;
        for(int j=1;j<=cnt&&i<=n/p[j];++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]-=mu[i];
        }
    }
}