什么是莫比乌斯反演?

如果存在两个数论函数$f(x),g(x)$满足$$f(n)=\sum_{d|n}g(d)$$则有$$g(n)=\sum_{d|n}\mu(d)\cdot f(\frac{n}{d})$$

前置知识

莫比乌斯函数

莫比乌斯函数的定义为$$\mu(n) = \begin{cases}1&n=1\\(-1)^{k}&n=\prod p_i&p_i\in{prime}~\&~p_i\ne p_j\\0&otherwise\end{cases}$$

性质

  1. $$\sum\limits_{d | n} \mu(d) = [n = 1]$$

    若n=1,显然成立。

    若n>1,因为$n=\prod\limits_{i=0}^kp_i^{a_i}$,其中若$\mu(d)\ne0$则$d=\prod\limits_{i=0}^{k'}p'_i(p'\subset p)$,即d由若干不重复素因子组成。此时考虑d可分解为的素因子个数r,可分解为r个素因子的因数共有$\binom{k}{r}$个,因此上式可化为$$\sum\limits_i^k\binom{k}{i}(-1)^i$$

    根据二项式定理$$(x + y) ^ n = \sum\limits_{i = 0}^{n}\binom{n}{i}x^iy^{n-i}$$这里我们令x=1,y=-1代入得到的式中得证。

  2. $$\sum\limits_{d | n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$

    需要用到狄利克雷卷积

    这里是大佬的学习笔记DimensionTripper-狄利克雷卷积学习笔记

    一些结论:$$f*\epsilon=f\\\mu*I=\epsilon$$

    将欧拉函数性质写成卷积形式$$\varphi*I=N$$然后进行变形$$\varphi*I*\mu=N*\mu\\\varphi*(I*\mu)=\varphi*\epsilon\to\varphi=N*\mu$$

    展开得$$\varphi(n)=\sum\limits_{d|n}\mu(d)N(\frac{n}{d})$$两边同除以n得$$\frac{\varphi(n)}{n}=\sum\limits_{d|n}\frac{\mu(d)}{d}$$

狄利克雷卷积

积性函数

对于数论函数$f$,若$f(a)\cdot f(b)=f(ab)~~\forall a, b~gcd(a,b)=1$则$f$为积性函数。

若$f(a)\cdot f(b)=f(ab)~~\forall a,b\in\N^+$则$f$为完全积性函数。

常见积性函数表
$\varphi(n)$欧拉函数,计算与n互质的正整数之数目
$\mu(n)$莫比乌斯函数,关于非平方数的质因子数目
$gcd(n,k)$最大公因子,当k固定的情况
$d(n) $n的正因子数目
$\sigma(n)$约数和函数。表示$n$ 的各个约数之和,即$\sigma(n)=\sum\limits_{d|n}d$
$I(n)$不变的函数,定义为$I(n)=1$(完全积性)
$N(n)$单位函数,定义为$N(n) = n$(完全积性)
$\epsilon(n)$元函数,定义为:若$n = 1,\epsilon(n)=1$;若$n>1,\epsilon(n)=0$。别称为“对于狄利克雷卷积的乘法单位”(完全积性)

什么是狄利克雷卷积

我们定义$f,g$两个函数的狄利克雷卷积$(*)$运算为$$(f*g)(n) = \sum \limits_{d|n} {f(d)g(\frac{n}{d})}$$(读作$f$卷$g$)。

狄利克雷卷积满足以下运算规律$$交换律:f*g=g*f\\结合律:f*(g*h)=(f*g)*h\\分配率:(f+g)*h=f*h+g*h$$

和算术乘法类似。

然后,狄利克雷卷积有一个非常重要的性质:

如果$f$和$g$均为积性函数,那么$f*g$一定也为积性函数。

证明:

$$h=f*g=\sum\limits_{d|n}f(d)g(\frac{n}{d})=\sum\limits_{i_1=0}^{k_1}\sum\limits_{i_2=0}^{k_2}f(p_1^{i_1})f(p_2^{i_2})g(p_1^{k_1-i_1})g(p_2^{k_2-i_2})\\=\left[\sum\limits_{i_1=0}^{k_1}f(p_1^{i_1})g(p_1^{k_1-i_1})\right]\cdot\left[\sum\limits_{i_2=0}^{k_2}f(p_2^{i_2})g(p_2^{k_2-i_2})\right]=h(p_1^{k_1})h(p_2^{k_2})=h(n)$$

应用

关于莫比乌斯函数有一个重要等式:由莫比乌斯函数的性质一$\sum\limits_{d | n} \mu(d) = [n = 1]$转化为狄利克雷卷积的形式可以写作$\mu * I = \epsilon$,接下来我们可以凭此证明莫比乌斯反演。

由于积性函数的性质,证明积性函数$f_x$只需证明$f_p(p为素数)$

莫比乌斯反演

待填坑

 

前缀和

线性筛

杜教筛

题目列表

参考资料

@DimensionTripper的莫比乌斯反演学习笔记

@ViXbob的「莫比乌斯反演」学习笔记

@Edgration的Summary Math(3) 莫比乌斯反演

本蒟蒻郑重感谢各位大佬的鼎力支持orz。

keyboard_arrow_up