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

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

$$ \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 $$

$$ \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\qquad\qquad\quad n=1\\0\qquad\qquad\quad \exist d>1:d^2|n\\(-1)^{\omega(n)}\qquad otherwise\end{array}\right.$ 其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数, 是一个积性函数

定义两个数论函数 $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) $$