数论 莫比乌斯函数及莫比乌斯反演(mo and Möbius inversion formula)

· · 个人记录

一.莫比乌斯函数

1.定义

莫比乌斯函数的定义如下 [1] :

用人话解释就是假如有一个数x把它质因数分解后：

x=p_1^{a_1} \times p_2^{a_2} \cdots p_n^{a_n}

如果所有a_i都为1 那么\mu(x)=(-1)^n

否则 \mu(x)=0

2.性质

莫比乌斯函数有一个非常重要的性质：

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

换句话说就是一个不是1的数它所有因子的\mu之和为0

我们假设n=p_1^{a_1} \times p_2^{a_2} \times \cdots p_k^{a_k} (p_i是质数)

那么对于所有因子有完全平方数的d \mu(d)=0不对和产生影响

因此只要考虑那些不包含完全平方数因子的d的\mu

这个问题可以看成:

从k个不同的质因数中选择若干

\sum_{d|n}\mu (d)=C_k^0 \times (-1)^0+C_k^1 \times (-1)^1 +\cdots C_k^k \times (-1)^k

而这条式子根据二项式定理就是(1-1)^k(你可以把结果展开看看对不对)

因此若k=0即n=1,\sum_{d|n}\mu (d)=1

若k \not= 0即n\not=1,\sum_{d|n}\mu (d)=0

3.计算

根据莫比乌斯函数的定义可以得到一个有趣的结论：

对于任意实数n和与n互质的质数p \;满足\mu(n\times p)=-\mu(n)

这分\mu(n)=0与\mu(n)\not=0讨论一下便知都成立

这个条件不就很欧拉筛吗 （欧拉筛）

因此我们就用欧拉筛求莫比乌斯函数

code

a[1]=mu[1]=1;
for(register int i=2;i<=n;i++){
    if(!a[i]){
        f[++f[0]]=i;
        mu[i]=-1;
    }
    for(register int j=1;j<=f[0];j++){
        if(f[j]*i>=n) break;
        a[i*f[j]]=1;
        if(i%f[j]==0) break;
        mu[i*f[j]]=-mu[i];
        //注意这里的mu是在判断整除的后面 刚好整除的情况是有完全平方数的 
    }
}

二.莫比乌斯反演

莫比乌斯函数最主要的应用就是莫比乌斯反演

而莫比乌斯反演是数论数学中极为重要的一部分

所谓反演其实类似于求一个函数的反函数

由得到的函数反推出初始的函数的过程

1.定理

形式1

若有

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

则有

f(n)=\sum_{d|n}\mu(\dfrac{n}{d})F(d)=\sum_{d|n}\mu(d)F(\dfrac{n}{d})

形式2

若有

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

则有

f(n)=\sum_{n|d} \mu(\dfrac{d}{n})F(d)

2.证明

莫比乌斯反演的定理有两种证明方法 定义法和狄利克雷法

定义法不需要学任何前置知识

狄利克雷法几乎不需要懂脑子（）

(1)定义法（因为我看别人博客没看懂所以写详细一点）

我们不妨把从右往左推

\sum_{d|n}\mu(d)F(\dfrac{n}{d})&=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)\\ &=\sum_{k|n}f(k) \sum_{d| \frac{n}{k}}\mu(d) \\&=\sum_{k|n} f(k)\times [\dfrac{n}{k}=1]\\ &=f(n) \end{aligned}

解释一下

第一个等号是把F的定义代入进去

看到n无非就是kd的倍数 所以换个顺序也无妨

第三个等号就是莫比乌斯函数性质

而由于当且仅当k=n时\frac{n}{k}=1

所以原式就等于f(n)

同样的

\sum_{n|d} \mu(\dfrac{d}{n})F(d)&=\sum_{k=1}^{+\infty}\mu(k)F(nk)\\ &=\sum_{k=1}^{+\infty}\mu(k)\sum_{nk|t}f(t)\\ &=\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)\\ &=\sum_{n|t}f(t)[\dfrac{t}{n}=1]\\ &=f(n) \end{aligned}

也稍微解释一下

第一步用k换掉\dfrac{t}{n} 第二步打开F(nk)

第三步换顺序 t是nk的倍数 那么k就是\dfrac{t}{n}的因数

第四步性质 第五步只有t=n时括号内才为1所以就是f(n)

(2)狄利克雷法

\cdots

3.习题(持续添加中)

YY的GCD

约数个数和

三.总结

莫比乌斯函数一般是为莫比乌斯反演服务的

而莫比乌斯反演一般用于处理gcd问题

是一个由结果推源头的过程

Finally，谢谢大家

（如果对内容有争议请指出）

参考内容

[1]莫比乌斯反演[OL].百度百科.2021-03-30/2021-05-26.

[2]pengym.莫比乌斯反演[OL].博客园.2018-03-26/2021-05-26

[3]alpc_qleonardo.莫比乌斯反演的两种形式及其证明[OL].CSDN.2018-07-28/2021-05-26