$$莫比乌斯反演$$

$莫比乌斯函数$

$\mu (n) \left\{ \begin{array}{a} 1 (n = 1) \\ 0 (n含有平方因子)\\ (-1)^k (n含有k个质因子) \\ \end{array} \right.$

$引理1$

$n = \Pi_{i=1}^{k}Pi^{Ci}， n’= \Pi_{i=1}^{k}Pi$

$则S(n) = \sum_{i \mid n}\mu (i)$

$= \sum_{i \mid n’}\mu (i)$

$= \sum_{i=1}^k C^i_k *(-1)^i$

$=(1 + (-1)) ^ k$

$= 0$

$即S (n) \left\{ \begin{array}{a} 1 (n=1)\\ 0 (n>1) \\ \end{array} \right.$

$莫比乌斯反演$

定义函数$f(n)$, $F(n)$

(1).若$F(n) = \sum_{d\mid n}f(d)$,则$f(n)=\sum_{d\mid n}\mu (d) F(\frac{n}{d})$

$证明$

$\sum_{d\mid n}\mu (d) F(\frac{n}{d})$

$= \sum_{d\mid n}\mu (d) \left( \sum_{i\mid \frac{n}{d}}f(i) \right)$

$= \sum_{i \mid n} f(i) \left( \sum_{d \mid \frac{n}{i}}\mu (d) \right)$

$= \sum_{i \mid n} f(i) S(\frac{n}{i})$

$= f(n)$

证毕

(2).若$F(n) = \sum_{n\mid d}f(d)$,则$f(n)=\sum_{n\mid d}\mu (\frac{d}{n}) F(d)$

$证明$

$\sum_{n\mid d}\mu (\frac{d}{n}) F(d)$

$= \sum_{n\mid d}\mu (\frac{d}{n}) \left( \sum_{d\mid i}f(i) \right)$

$= \sum_{n \mid i}f(i)\left( \sum_{\frac{d}{n} \mid \frac{i}{n}}\mu (\frac{d}{n}) \right)$

$= \sum_{n \mid i}f(i)\left( \sum_{d’ \mid \frac{i}{n}}\mu (d’) \right)$

$= \sum_{n \mid i}f(i)S(\frac{i}{n})$

$= f(n)$

证毕

$例题$

1.Problem b
2.约数个数和