# 路终会有尽头，但视野总能看到更远的地方。

0%

## 莫比乌斯函数

$x$的莫比乌斯函数记为$\mu(x)$。

$i$ $\mu(i)$ $i$ $\mu(i)$ $i$ $\mu(i)$ $i$ $\mu(i)$
$1$ $1$ $5$ $-1$ $9$ $0$ $13$ $-1$
$2$ $-1$ $6$ $1$ $10$ $1$ $14$ $1$
$3$ $-1$ $7$ $-1$ $11$ $-1$ $15$ $1$
$4$ $0$ $8$ $0$ $12$ $0$ $16$ $0$

### 莫比乌斯反演

#### 反演步骤

1. 准备过程，列出$f$函数关于$g$函数的方程。即$f(n)=?g(n)$。
2. 说废话（将$g(n)$转为$bool$表达式）：$g(n)=\sum[i=?]g(i)$
3. 利用恒等式代换。
4. 交换$\sum$下标
5. 利用$f(n)$进行代换

#### 两类莫比乌斯反演

$f(n)=\sum_{d\mid n}g(d) \rightarrow g(n)=\sum_{d\mid n}\mu(d)f(\frac nd)$

$f(n)=\sum_{n\mid d}^Ng(d)\rightarrow g(n)=\sum_{n\mid d}^Nf(d)\mu(\frac dn)$

### 莫比乌斯反演的应用

$\varphi$可以使用线性筛预处理处理，我们就可以枚举$T$求上式了，时间复杂度$O(n)$。

## 参考资料

• 莫比乌斯反演.pptx - liuguangzhe
• Bill_Yang莫比乌斯反演笔记手稿