学习笔记_莫比乌斯反演

Neck Deep / 2023-08-11 / 原文

前置知识：整除分块

莫比乌斯函数($\mu$)

$\mu(d)=\begin{cases}
1 & (d=1)
\\
(-1)^{k} & \forall C_i=1
\\
0 & \exists C_i>1
\end{cases} $

性质

1.对于任意正整数$n$,$$\sum_{d|n} \mu(d) = [n=1]$$
[]是一个返回bool型值的判断，当[]内条件成立时返回1，否则返回0.

2.对于任意正整数$n$,

\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} \]

代码实现


int num_prime;
//质数个数
bool noprime[N];
//判断每个数是否是质数
int mu[N],prime[N];
//mu[]莫比乌斯函数   prime[]质数

void Wonder_of_U(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;++i)
    {

        if(!noprime[i])
        {
            p[++num_prime]=i;
            mu[i]=-1;
        }
        for(int j=1,k;j<=num_prime && (k=i*prime[j])<=n;++j)
        {
            noprime[k]=true;
            if(!(i % prime[j]))break;
            else mu[k]=-mu[i];
        }
    }
}

莫比乌斯反演

莫比乌斯定理

定义$F(n)$和$f(n)$是定义在非负整数集合上的两个函数。他们满足：

\[F(n)= \sum_{d|n} f(d) \]

那么一定存在

\[f(n)=\sum_{d|n}\mu(d)F(\lfloor \frac nd \rfloor) \]

此即为莫比乌斯定理.

证明

由$F(n)$和$f(n)$定义可得

\[F(\lfloor \frac nd \rfloor)=\sum_{i|{\lfloor \frac nd \rfloor}}f(i) \]

那么

\[\sum_{d|n}\mu(d)F(\lfloor \frac nd \rfloor)=\sum_{d|n}\mu(d)\sum_{i|{\lfloor \frac nd \rfloor}}f(i)=\sum_{i|n}f(i) \sum_ {d|{\lfloor \frac ni\rfloor}}\mu(d)=f(n) \]

证毕.

还有个式子.
当$F(n)$和$f(n)$满足

\[F(n)=\sum_{n|d}f(d) \]

得到

\[f(n)=\sum_{n|d}\mu (\frac dn)F(d) \]