RainAir
My OI Blog
RainAir
「数学基础」莫比乌斯反演
「数学基础」莫比乌斯反演

UPD:狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。

积性函数

定义

对于一个函数 $f$,若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$,则我们称这样的函数为积性函数。
举例:$\phi(x),\mu(i),d_k(n)$($n$ 的所有正因子 $k$ 次幂和)

性质

若 $f(x)$ 为积性函数。
设 $n = \Pi p_i^{q_i}$,则有 $f(n) = \Pi f(p_i^{q_i})$。
这告诉我们大多数的积性函数都可以用线性筛来处理。
若 $f(x),g(x)$ 均为积性函数,那么下列的函数也是积性函数:
$$(fg)(n) = f(n)*g(n)$$
$$(f/g)(n) = f(n)/g(n)$$

Dirichlet 卷积

定义

定义在两个数论函数之间的运算 $\times$ 为:
$$(f \times g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})$$
该运算满足交换律,结合律,分配律。
如果 $f,g$ 均为积性函数,那么 $f\times g$ 也是个积性函数。

单位元

定义 Dirichlet 卷积运算的单位元 $\iota(n)$。
显然该函数当 $n=1$ 的时候取 $1$,其他情况取 $0$。
一些关于单位元的例子:
对于任何数论函数 $f$, $f\times \iota = f$
单位元 $\iota = \mu \times i$
因数个数 $d = 1\times 1$
因数和 $\sigma = n\times 1$
欧拉函数 $\phi = mu \times ID$
定义一下函数乘法单位元 $u$ ,显然 $u(n) = 1$。

莫比乌斯函数

构造一个函数 $\mu$,使得 $\mu \times u = \iota$。
$\mu(x)$ 的取值:
如果 $x = 1,\mu(x) = 1$
如果 $x$ 含有平方因子,则 $\mu(x) = 0$
否则 $\mu(x) = (-1)^k$,$k$ 是 $x$ 的本质不同质因子个数。
易得 $\mu$ 是一个积性函数,可以用线性筛得到。
代码:

接下来我们尝试证明 $\phi \times 1 = ID$,其中 $ID$ 为 $f(x) = x$。

首先由于 $\phi$ 是个积性函数,于是我们只需要证明当 $x’ = p^c$ 时 $\mu \times 1 = \sum_{ d | x’ } \phi ( \frac{ x’ }{ d } ) = ID $ 成立即可。

因为 $p$ 是个质数,所以有 $d = p^0,p^1,p^2,…,p^c$。

随手推下式子:
$$ \phi \times i = \sum_{d | n} \phi( \frac{n}{d} )$$
$$ = \sum_{i=0}^c \phi(p^i)$$
$$ = 1 + (p-1) * \sum_{i=0}^c p^i$$
$$= p^c$$
$$= ID$$

莫比乌斯反演

现在我们来看看莫比乌斯反演讲了什么。
$$ f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n} \mu(\frac{n}{d}) f(d) $$
写成卷积形式,即
$$f = g \times u \Leftrightarrow g = f \times \mu$$
我们来证明一下:
左边:
$$f = g \times u$$
$$\Rightarrow f \times \mu = g\times u\times \mu$$
$$\Rightarrow f\times \mu = g\times \iota$$
$$\Rightarrow f\times \mu = g$$
右边:
$$g = f\times \mu$$
$$\Rightarrow g\times u = f\times \mu*u$$
$$\Rightarrow g\times u = f\times \iota$$
$$\Rightarrow f = g\times u$$
证毕。
莫比乌斯反演的另一种常用形式:
$$ f(n) = \sum_{n|d} g(d) \Leftrightarrow g(n) = \sum_{n|d} \mu(\frac{d}{n}) f(d)$$。
接下来我们以一道例题来具体分析如何使用莫比乌斯反演解决问题。

「BZOJ 2820」YY 的 GCD

题目链接
注意:接下来所有的除法都向下取整。
定义质数组成的集合 $prime$,不难看出题目需要求:
$$\sum_{i=1}^n \sum_{j=1}^m [(i,j) \in prime] \tag 1$$
我们套路的设 $f(x)$ 表示 gcd 为 $x$ 的对数,即
$$f(x) = \sum_{i=1}^n \sum_{j=1}^m [(i,j)=x]$$
设 $F(x)$ 表示 gcd 为 $x$ 及 $x$ 的倍数的对数,即
$$F(x) = \sum_{x|d} f(d)$$
不难得出 $F(x) = \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor$
根据莫比乌斯反演,可得
$$f(x) = \sum_{n|d} \mu(\frac{d}{n})F(d)$$
我们把 $(1)$ 式首先改为枚举质数 $p$。
$$Ans = \sum_{p \in prime}^{max(n,m)} \sum_{i=1}^n \sum_{j=1}^m [(i,j = p)]$$
代入 $f$,得
$$Ans = \sum_{p \in prime}^{max(n,m)} f(p)$$
然后根据上面莫比乌斯反演得到的结论,式子转化为
$$Ans = \sum_{p \in prime}^{max(n,m)} \sum_{p|d} \mu(\frac{d}{p})F(d)$$
我们枚举 $\frac{d}{p}$,得:
$$Ans = \sum_{p \in prime} \sum_{d=1}^{min(\frac{n}{p},\frac{m}{p})} \mu(d) F(dp) = \sum_{p \in prime} \sum_{d=1}^{min(\frac{n}{p},\frac{m}{p})} \mu(d) \lfloor \frac{n}{dp} \rfloor \lfloor \frac{m}{dp} \rfloor$$
设 $dp = T$,则

$$Ans = \sum_{T=1}^{ min(n,m) } \sum_{t|T,t \in prime} \mu(\frac{T}{t}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$$
$$Ans = \sum_{T=1}^{min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor (\sum_{t|T} \mu(\frac{T}{t}))$$
推到这里我们已经可以通过预处理 $\mu$ 函数来 $O(n)$ 的做了。但是这一题是多组询问,注意到有除法,那么我们使用数论分块来使复杂度降低到 $\sqrt{n}$,处理个前缀和就可以了 $qwq$。

总结:

可以把莫比乌斯反演理解成 “由大推小” ,即知道了如何 “由小推大” 后通过 $\mu$ 函数(可以理解为容斥系数)来快速求出小的函数。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/412
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「数学基础」莫比乌斯反演
UPD:狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。 积性函数 定义 对于一个函数 $f$,若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$,则我们称这样的函数为积性函数。 举例:$…
扫描二维码继续阅读
2019-01-14
标签
近期评论