0.前言

老年退役选手的消遣

1.莫比乌斯函数

\(\mu\)或莫比乌斯函数是指以下函数：

\[\mu(n) = \left\{ \begin{aligned} 1 \quad\qquad\qquad \qquad \qquad \qquad \qquad n = 1 \\ \quad \qquad (-1)^k \qquad n = p_1 p_2...p_k, p_i为互不相同的素数 \\ 0 \quad\qquad\qquad\qquad n含有指数大于1的质因子 \end{aligned} \right. \]

莫比乌斯函数的性质：
性质1：对于任意正整数n：

\[\sum_{d\mid n} \mu(n) = \left\{ \begin{aligned} 1 \qquad n = 1 \\ 0 \qquad n > 1 \end{aligned} \right. \]

性质2：对于任意正整数n：

\[\sum_{d \mid n} \frac{\mu(d)}{d} = \frac{\phi(n)}{n} \]

性质2推论：

\[\sum_{d \mid n} d\cdot \mu(\frac{n}{d}) = \phi(n) \]

证明： 令\(k = \frac{n}{d}\)，带入原式，易得。
线性筛求\(\mu\)：

咕咕咕

2.莫比乌斯反演

设\(f(n), F(n)\) 为定义在正整数集合上的函数。
若\(F(n)\)满足：

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

则：

\[f(n) = \sum_{d \mid n} \mu(d)F(\frac{n}{d}) \]

或：

\[f(n) = \sum_{n \mid d} \mu(\frac{d}{n})F(d) \]

前一个式子证明：（使用定义法）

\[右 = \sum_{d \mid n} \mu(d)F(\frac{n}{d}) = \sum_{d \mid n}\mu(d)\cdot \sum_{k \mid \frac{n}{d}}f(k) = \sum_{k \mid n} f(k) \cdot \sum_{d \mid \frac{n}{k}} \mu(d) = f(n) = 左 \]

证毕。（第三个等号看不明白可以代个数算算，可以发现两边正好相等）
（也可以使用狄利克雷卷积证明）

3.题目：

咕咕咕