初等数论入门 Lesson 4 莫比乌斯反演

线性筛求 μ(1…n)

• $\mu(1)=1$
• 若 $i$ 是素数：$\mu(i)=-1$
• 若 $i\mod p_j=0$，即 $p_j^2\mid i$，则 $\mu(i\cdot p_j)=0$
• 否则：$\mu(i\cdot p_j)=-\mu(i)$

基础函数与Dirichlet卷积

• 单位函数（卷积单位元）

$$\varepsilon(n)= \begin{cases} 1, & n=1 \\ 0, & n>1 \end{cases}$$

满足 $\varepsilon * f=f*\varepsilon =f$

• 常值函数 1

$$1(n)\equiv 1$$

故：

$$(1*f)(n)=\sum_{d\mid n}f(d)$$

μ 与常值函数 1 互逆

$$\sum_{d\mid n}\mu(d)= \begin{cases} 1, & n=1 \\ 0, & n>1 \end{cases}$$

卷积形式：

$$\boxed{\mu * 1=\varepsilon=1*\mu}$$

证明：

$$\sum_{d\mid n}\mu(d)=\sum_{r=0}^k\binom k r (-1)^r=(1-1)^k=0$$

重要性：

定义：

$$F(n)=(1*f)(n)=\sum_{d\mid n}f(d)$$

则：

$$(\mu * F)(n)=(\mu * (1*f))(n)=((\mu * 1)*f)(n)=\varepsilon *f=f(n)$$

本质：

$\mu$ 是常值函数 1 在 Dirichlet卷积下的逆元

莫比乌斯反演定理

整除型

若：

$$F(n)=\sum_{d\mid n}f(d)$$

则

$$\boxed{f(n)=\sum_{d|n}\mu(d)F\left(\frac n d\right)}$$

倍数型

若：

$$F(n)=\sum_{n\mid d,d\le N}f(d)$$

则：

$$\boxed{f(d)=\sum_{n\mid d,d\le N}\mu\left(\dfrac d n\right)F(d)}$$

数论分块

对于：

$$\sum_{i=1}^n\left\lfloor\dfrac n i\right\rfloor$$

由于 $\left\lfloor\dfrac n i\right\rfloor$ 随着$i$ 增大，会变化非常慢，会一大段一大段保持不变。

假设这一段从 $i$ 开始，则在 $\left\lfloor\dfrac n {\lfloor n/i\rfloor}\right\rfloor$ 结束

容斥视角：统计互素数对

求 $1\le i\le n,\;1\le j\le n$，满足 $\gcd(i,j)=1$ 的 $(i,j)$ 个数。

设：

$$F(d)=\#\{(i,j):d\mid \gcd(i,j)\}=\left\lfloor \dfrac n d\right\rfloor^2$$

我们要求：

$$f(d)=\#\{(i,j):\gcd(i,j)=1\}$$

则：

$$f(1)=\sum_{d=1}^n\mu(d)F(d)=\sum_{d=1}^n\mu(d)\left\lfloor \dfrac n d\right\rfloor^2$$

（$d$ 从 $1\to n$ 的原因是任意 $d$ 均有 $1|d$）

其中最后的式子我们可以用整除分块来处理。

可以看出，莫比乌斯反演是容斥原理在数论函数上的表达，而μ函数就是容斥系数。