莫比乌斯反演

简介

莫比乌斯反演是数论中的重要内容. 对于一些函数 $f(n)$, 如果很难直接求出它的值, 而容易求出其倍数和或约数和 $g(n)$, 那么可以通过莫比乌斯反演简化运算, 求得 $f(n)$ 的值

开始学习莫比乌斯反演前, 我们需要一些前置知识: 积性函数、Dirichlet 卷积、莫比乌斯函数.

前置知识

引理 1

$$ \forall a,b,c\in Z,\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor $$

引理 2

$$ \forall n\in N,\left|\left\{\left\lfloor\frac{n}{d}\right\rfloor|d\in N\right\}\right|\le\left\lfloor2\sqrt{n}\right\rfloor $$

$|V|$ 表示集合 $V$ 的元素个数

数论分块

数论分块的过程大致如下: 考虑含有 $\left\lfloor\frac{n}{i}\right\rfloor$ 的求和式子 ( $n$ 为常数)

对于任意一个 $i$ ( $i\le n$ ), 我们需要找到一个最大的 $j$ ( $i\le j\le n$ ), 使得 $\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{j}\right\rfloor$.

而 $j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$.

利用上述结论, 我们每次以 $[i,j]$ 为一块, 分块求和即可

积性函数

定义

若 $gcd(x,y)=1$ 且 $f(xy)=f(x)f(y)$, 则 $f(n)$ 为积性函数.

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数, 则以下函数也为积性函数: $$ h(x)=f(x^p)\\ h(x)=f^p(x)\\ h(x)=f(x)g(x)\\ h(x)=\sum_{d|x}f(d)g(\frac x d) $$

例子

单位函数: $\varepsilon(n)=[n=1]$

恒等函数: $id_k(n)=n^k, id_1(n)$ 通常简记为 $id(n)$

常数函数: $1(n)=1$

除数函数: $\sigma_k(n)=\sum_{d|n}d^k$, $\sigma_0(n)$ 通常简记作 $d(n)$ 或 $\tau(n)$, $\sigma_1(n)$ 通常简记作 $\sigma(n)$

欧拉函数: $\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]$

莫比乌斯函数: $\mu(n)=\left\{\begin{array}{}1&n=1\\0&存在 d>1:d^2|n\\(-1)^{\omega(n)}&otherwise\end{array}\right.$ 其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数, 是一个积性函数

Dirichlet 卷积

定义

定义两个数论函数 $f,g$ 的 $Dirichlet$ 卷积为 $$ (f*g)(n)=\sum_{d|n}f(d)g(\frac n d) $$

性质

$Dirichlet$ 卷积满足交换律和结合律

其中 $\varepsilon$ 为 $Dirichlet$ 卷积的单位元 (任何函数卷 $\varepsilon$ 都为其本身)

例子

$$ \varepsilon=\mu*1\Longleftrightarrow\varepsilon(n)=\sum_{d|n}\mu(d)\\ d=1*1\Longleftrightarrow d(n)=\sum_{d|n}\\ \sigma=id*1\Longleftrightarrow\sigma(n)=\sum_{d|n}d\\ \varphi=\mu*id\Longleftrightarrow\varphi(n)=\sum_{d|n}d\cdot\mu(\frac n d) $$

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数, 定义为 $$ \mu(n)=\left\{ \begin{array}{l} 1&n=1\\ 0&n含有平方因子\\ (-1)^k&k为n的本质不同质因子个数 \end{array}\right. $$ 详细解释一下:

令 $n=\prod_{i=1}^kp_i^{c_i}$, 其中 $p_i$ 为质因子, $c_i\ge1$. 上述定义表示:

$n=1$ 时, $\mu(n)=1$;
对于 $n\ne1$ 时:
1. 当存在 $i\in[1,k]$, 使得 $c_i>1$ 时, $\mu(n)=0$, 也就是说只要某个质因子出现的次数超过一次, $\mu(n)$ 就等于 $0$;
2. 当任意 $i\in[1,k]$, 都有 $c_i=1$ 时, $\mu(n)=(-1)^k$, 也就是说每个质因子都仅仅只出现过一次时, 即 $n=\prod_{i=1}^kp_i$, $\{p_i\}_{i=1}^k$ 中各元素唯一时, $\mu(n)$ 等于 $-1$ 的 $k$ 次幂, 此处 $k$ 指的便是仅仅只出现过一次的质因子的总个数.

性质

莫比乌斯函数不但是积性函数, 还有如下性质: $$ \sum_{d|n}\mu(d)=\left\{ \begin{array}{l} 1&n=1\\ 0&n\ne1 \end{array}\right. $$ 即 $\sum_{d|n}\mu(d)=\varepsilon(n)$, 即 $\mu*1=\varepsilon$ $$ [gcd(i,j)=1]\Longleftrightarrow\sum_{d|gcd(i,j)}\mu(d) $$

$$ \varphi*1=ID $$

( $ID$ 函数即 $f(x)=x$ )

该式子两侧同时卷 $\mu$ 可得 $\varphi(n)=\sum_{d|n}d\cdot\mu(\frac{n}{d})$