学习笔记_莫比乌斯反演

标签：lfloor frac 乌斯 sum rfloor mu 反演 莫比

前置知识：整除分块

莫比乌斯函数(\(\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) \]

标签：lfloor,frac,乌斯,sum,rfloor,mu,反演,莫比
From： https://www.cnblogs.com/Cayde-6/p/17623827.html