反演（莫比乌斯反演、二项式反演）原理及应用
莫比乌斯函数（Möbius function）
定义
莫比乌斯函数\mu(n)定义为：
\mu(n) = \begin{cases} 1 & (n=1) \\ (-1)^k & (n = p_1p_2 \cdots p_k) \\ 0 & (p^k|n, k > 1) \end{cases}
文字描述是这样的。定义\mu(1)=1；如果n是k个互异的质因数的乘积，则\mu(n)=(-1)^k；如果n中含有一个质因数的次数超过1，则\mu(n)=0。
这是一个积性函数。
性质
- \sum_{d|n} \mu(d) = \begin{cases} 1 & (n=1) \\ 0 & (n \neq 1) \end{cases}
- \sum_{d|n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}
狄利克雷卷积（Dirichlet convolution）
定义
对于数论函数f(n)和g(n)，定义其狄利克雷卷积为
(f * g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})
性质
- 交换律：f * g = g * f
- 结合律：f * (g * h) = (f * g) * h
- 对加法的分配律：f * (g + h) = f * g + f * h
- 积性函数的点积和狄利克雷卷积也是积性函数
莫比乌斯反演（Möbius inversion）
假设数论函数f(n)与F(n)满足：F(n) = \sum_{d|n} f(d)，则
f(n) = \sum_{d|n} \mu(d) F(\frac{n}{d})
另外一种形式：
假设数论函数f(n)与F(n)满足：F(n) = \sum_{n|d} f(d)，则
f(n) = \sum_{n|d} \mu(\frac{d}{n}) F(d)
