莫比乌斯反演学习笔记

Posted on | Edited on | In | Views:

前言

停更好久了，刚好我们老师讲了莫比乌斯反演，那我就来开数论这个天坑吧。

莫比乌斯反演

比如说我们现在有一个函数$f(n)=\sum_{d|n}g(d)$
假设f非常容易求得，但是g很难求，那么我们是不是可以通过f来求g呢
$g(n)=\sum_{d|n}f(\frac{n}{d})*\mu(d)$
然后$mu(d)$这个东西就是莫比乌斯函数，所以这个变换也叫莫比乌斯变换

关于莫比乌斯函数

  1. 若 $d=1$，则 $\mu(d)=1$
  2. 若 $d=p_1*p_2*p_3*p_4*..*p_n$ (注意不是笔者偷懒，而是p的次数都是1，且都是互异的质数) 那么$\mu(d)=(-1)^{n}$
  3. other wise $\mu(d)=0$

    莫比乌斯函数的性质

性质1

对于正整数n，有$\sum_{d|n}\mu(d)=[n=1]$
中括号在这里表达bool表达式，如果满足中括号内的条件则为1，否则为0
证明：

  1. n=1，根据定义，显然成立
  2. n>1，设$n=p_1^{x_1}*p_2^{x_2}*p_3^{x_3}*…*p_k^{x_k}$，也就是把n质因数分解
    那么d一定能表示为$p_1^{y_1}*p_2^{y_2}*p_3^{y_3}*…*p_k^{y_k}$，其中($0\le y_i\le x_i$)，那么根据定义，只要有一个y大于二，那么$\mu(d)=0$，没有贡献，所以我们只要考虑所有y均为0,1时的情况。
    我们假设这k个中有r个y=1，那么出现这种情况的方案数为$C_{k}^{r}$，总贡献为
    $C_{k}^{r}*(-1)^{r}$
    我们再把每个d的贡献加起来$\sum_{r=0}^{k}*C_{k}^{r}*(-1)^{r}$
    是不是觉得有点眼熟呢，没错，这就是我们的二项式定理，所以上式就等于$(1+(-1))^k=0$
    结论得证。

性质2

莫比乌斯函数为积性函数
证明：
若有两个互质的数a,b
我们把它们分别分解质因数
$a=p_1^{x_1}*p_2^{x_2}*…*p_k^{x_k}$
$b=q_1^{y_1}*q_2^{y_2}*…*q_t^{y_t}$
由于a,b互质，$a*b=p_1^{x_1}*p_2^{x_2}*…*p_k^{x_k}*q_1^{y_1}*q_2^{y_2}*…*q_t^{y_t}$
如果$\mu(a)==0或\mu(b)==0$为0，那么说明一定有一个x或y>=2，那么$\mu(a*b)$也一定为0.
若$\mu(a)$与$\mu(b)$均为1，说明k与t均为偶数，那么k+t也为偶数，所以$\mu(a*b)$也为1
若$\mu(a)$与$\mu(b)$均为-1，说明k与t均为奇数，那么k+t为偶数，所以$\mu(a*b)$为1
若$\mu(a)为1，\mu(b)$为-1，说明k为偶数，t为奇数，那么k+t为奇数，所以$\mu(a*b)$为-1，
$\mu(b)为1，\mu(a)$为-1与上一条同理。
综上所述，莫比乌斯函数为积性函数。

莫比乌斯函数的求法

这里介绍一下如何使用线性筛筛出莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
mu[1]=1;
for (int i=2;i<=100000;i++){
    if (isprime[i]){prime[++pri]=i;mu[i]=-1;}//质数的mu显然是-1
    for (int j=1;j<=pri&&i*prime[j]<=100000;j++){
        int tt=i*prime[j];
        isprime[tt]=0;
        if (i%prime[j]==0){//说明prime[j]这个质因子次数大于1，所以mu为0
            mu[tt]=0;
            break;
        }
        else{
            mu[tt]=-mu[i];//说明新出现了一个质数，所以要再*=-1
        }
    }
}

其复杂度就是线性筛的复杂度，和筛质数，筛phi都是一样的。

莫比乌斯反演

我们现在已经知道了莫比乌斯函数和他的一些性质，那么我们试着证明一下莫比乌斯反演的正确性。

$g(n)=\sum_{d|n}f(\frac{n}{d})*\mu(d)$
再把$f$展开

然后我们把g的sigma换到前面去

我们考虑后面这个sigma的值
1.当i=n时，$\sum_{d|\frac{n}{i}}\mu(d)=1，g(i)\sum_{d|\frac{n}{i}}\mu(d)=g(n)$
2.当i为小于n且是n的因数时，根据$\sum_{d|n}\mu(d)=[n=1]$
那么$\sum_{d|\frac{n}{i}}\mu(d)=0$，
乘上一个g(i)仍然为0，那么上下两种情况加起来就是$\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}g(i)$
所以就是g(n)，证毕

莫比乌斯反演的变形

变形一：$f(i)=\sum_{d=1}^{\lfloor{\frac{n}{i}}\rfloor}g(d*i)—->g(i)=\sum_{d=1}^{\lfloor{\frac{n}{i}}\rfloor}f(d*i)*\mu(d)$
证明：
我们把上面二式的f展开
$\sum_{d=1}^{\lfloor{\frac{n}{i}}\rfloor}f(d*i)*\mu(d)=\sum_{d=1}^{\lfloor{\frac{n}{i}}\rfloor}\mu(d)
\sum_{d1=1}^{\lfloor{\frac{n}{d*i}}\rfloor}g(d1*d*i)$
我们令d1*d=T
那么原式=$\sum_{T=1}^{\lfloor{\frac{n}{i}}\rfloor}g(T*i)
\sum_{d|T}\mu(d)$
仔细想一下i,d,T的关系应该不难理解
当(1)T=1时，$\sum_{d|T}\mu(d)=1，g(T*i)
\sum_{d|T}\mu(d)=g(i)$
(2)T>1时，$\sum_{d|T}\mu(d)=0，g(T*i)
\sum_{d|T}\mu(d)=0$
综上所述，结论正确
变形二：$f(i)=\sum_{i|d}g(d)—->g(i)=\sum_{i|d}f(d)*\mu(\frac{d}{i})$
证明：
另$\frac{d}{i}=k$
那么$\sum_{i|d}f(d)*\mu(\frac{d}{i})=\sum_{k=1}^{\infty}\mu(k)*f(k*i)=\sum_{k=1}^{\infty}\mu(k)*\sum_{k*i|t}g(t)=\sum_{i|t}*g(t)*\sum_{k|\frac{t}{i}}\mu(k)$
又是熟悉的套路，就是把$\mu$换成前缀和，就有非常好的性质了，那么最后得到的这个式子，只有在t=i时，后面的这个$\mu$的sigma才会变成1，所以加起来就是f(i)。

尾声

以上就是笔者对莫比乌斯反演的一些理解与介绍，军训每天逃机房花了5天终于码完了，希望能给大家带来帮助