莫比乌斯反演总结

Posted on 2018-05-23 Symbols count in article: 1.5k Reading time ≈ 5 mins.

$\;$

算术函数

定义

定义域为正整数、函数值为复数的函数叫算术函数，即映射 $f:\N\to\C$ 。
例如：

0(n)=0\\ 1(n)=1\\ \delta(n)= \begin{cases} 1&{n=1}\\ 0&{n\ge2}\\ \end{cases}

算术函数间的运算

相加： $(f+g)(n)=f(n)+g(n)$
相乘： $(f\cdot g)(n)=f(n)\cdot g(n)$
狄利克雷卷积： $(f\otimes g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)$ $(f \otimes g) (n) = \sum_{d ∣ n} f (d) g (\frac{n}{d}) = \sum_{d ∣ n} f (\frac{n}{d}) g (d)$
卷积的性质：
- 交换律： $f\otimes g=g\otimes f$
- 结合律： $(f\otimes g)\otimes h=f\otimes (g\otimes h)$
- 分配律： $f\otimes (g+h)=f\otimes g+f\otimes h$
- 单位元 $\delta$ ： $f\otimes\delta=f=\delta\otimes f$
- 逆元：对于 $f$ ， $\exists f^{-1}$ 使得 $f\otimes f^{-1}=\delta$

莫比乌斯函数与反演

定义

\mu(n)= \begin{cases} 1&&{n=1}\\ (-1)^k & & {n=p_1\times p_2\times\cdots\times p_k}\\ 0& & {\exists{p}满足p^2|n} \end{cases}

性质

结论1： $\sum_{d|n}\mu(d)=\delta$
证明：
设 $s$ 为 $n$ 的质因子个数， $w(x)$ 为 $x$ 的质因子个数
令 $rad(n)$ 为 $n$ 的所有质因子之积，即若 $n=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_s^{k_s}$ ，则 $rad(n)=p_1\times p_2\times\cdots\times p_s$
当 $n=1$ 时， $\sum_{d|1}\mu(d)=\mu(1)=1$
当 $n>1$ 时，

\begin{aligned} \sum_{d|n}\mu(d)&=\sum_{d|rad(n)}\mu(d)\\ &=\sum_{i=1}^{s}\sum_{d|rad(n),w(d)=i}\mu(d)\\ &=\sum_{i=1}^{s}\binom{s}{i}(-1)^i\\ &=\sum_{i=1}^{s}\binom{s}{i}\cdot1^{i}\cdot(-1)^{s-i}\\ &=(1-1)^s\\ &=0\\ \end{aligned}

推论： $\mathrm{LHS}=\mu\otimes1,\;\mathrm{RHS}=\delta$ ， $\therefore\;\mu\otimes 1=\delta,\;\mu^{-1}=1$

结论2（反演定理）：

若 $g(n)=\sum_{d|n}f(d)$ ，则 $f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$
若 $f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$ ，则 $g(n)=\sum_{d|n}f(d)$

即 $g=f\otimes 1\iff f=g\otimes \mu$

证明：

$\mathrm{RHS}=\mu\otimes g=\mu\otimes(1\otimes f)=(\mu\otimes 1)\otimes f=\delta\otimes f=f=\mathrm{LHS}$
$\mathrm{RHS}=f\otimes1=(g\otimes\mu)\otimes1=g\otimes(\mu\otimes1)=g\otimes\delta=g=\mathrm{LHS}$

莫比乌斯反演例题

基本套路

莫比乌斯反演题目是有转换套路的，一般只会用上述结论1，少数情况才会用结论二。

例：给定 $n,m,d$ ，求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]$
分析：
首先需要把 $[\gcd(i,j)=d]$ 化为我们熟悉的形式。我们有 $\delta(n)=[n=1]$ ，那么考虑将 $[\gcd(i,j)=d]$ 化为 $[\gcd(\frac{i}{d},\frac{j}{d})=1]$ ，于是 $原式=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(\frac{i}{d},\frac{j}{d})=1]$ ，当且仅当 $i,j$ 是 $d$ 的倍数时才会有意义。于是又转化为 $原式=\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(x,y)=1]$ 。
转化后就可以带入性质1（ $\mu\otimes1=\delta$ ）了，将后面的部分替换，可得到 $原式=\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{z|x,y}\mu(z)$ （这里 $z$ 为前面 $\gcd(x,y)$ 的值），接下来需要交换和号，即 $原式=\sum_{z=1}^{\min(n,m)}\mu(z)\sum_{x=pz}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=qz}^{\lfloor\frac{m}{d}\rfloor}1$ ，注意到后面 $\sum_{x=pz}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=qz}^{\lfloor\frac{m}{d}\rfloor}1$ 是可以直接计算的，其等价于 $x,y$ 的所有取值数对中 $x,y$ 均为 $z$ 的倍数的数对个数，所以 $\sum_{x=pz}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=qz}^{\lfloor\frac{m}{d}\rfloor}1=\lfloor\frac{n}{dz}\rfloor\cdot\lfloor\frac{m}{dz}\rfloor$ 。
我们已经得到了 $原式=\sum_{z=1}^{\min(n,m)}\lfloor\frac{n}{dz}\rfloor\cdot\lfloor\frac{m}{dz}\rfloor$ ，莫比乌斯反演已经转化完了。接下来是计算过程，需要用到数论分块。 $z$ 的取值一定能分为很多块，使得每块中 $\lfloor\frac{n}{dz}\rfloor$ 和 $\lfloor\frac{m}{dz}\rfloor$ 都相同。这样的块一定不会超过 $\sqrt{n}+\sqrt{m}$ 个，对于每个块，我们直接用后面乘式的积乘块大小得到贡献，然后每次用左端点取值找右端点即可。复杂度 $O(\sqrt{n}+\sqrt{m})$ 。

总结上述基本套路：

将和式的一部分转化为 $[x=1]$ 的形式，并将 $\sum_{d|n}\mu(d)=[n=1]$ 带入
将含 $\mu$ 的部分提到前面，并重新确定枚举的约数条件（易错）
观察 $\mu$ 后面的部分，找方法将其计算出来（直接算或预处理）
进行数论分块，对于每块用直接乘每个枚举量贡献或预处理前缀和求解

预处理积性函数

基本套路中， $1,2,4$ 条显然是很死板的，而 $3$ 灵活一些。如果 $\mu$ 后面的部分较为复杂，我们不能直接求值，那么如何计算呢？
积性函数：若数论函数 $f$ 满足对于所有 $\gcd(a,b)=1$ ，均有 $f(a\times b)=f(a)\times f(b)$ ，则称作积性函数。
完全积性函数：若数论函数 $f$ 满足 $\forall a,b,\;f(a\times b)=f(a)\times f(b)$ ，则称作完全积性函数。
我们将 $\mu$ 后面的部分分为一个或多个积性函数，若为完全积性函数则更好。分 $\gcd(a,b)$ 是否为 $1$ 推导一下 $f(a\times b)$ 的表达式，即可用线性筛线性预处理。
例：BZOJ2820 YY的GCD

积式中的莫比乌斯反演

有时，莫比乌斯反演会存在于积式中，作为底数或指数出现。
若为底数，则可以直接反演后计算，与和式中的方法类似。
若为指数，则会较为复杂。反演后将以莫比乌斯函数为指数的部分分离出来，想办法预处理其前缀积。
例：BZOJ4816【SDOI2017】数字表格

题目汇总