1 莫比乌斯函数定义
$$ \begin{aligned} \mu(x) &= 0 (存在\alpha[i]>=2) \\\\ &= (-1)^k (所有\alpha[i]==1) \\\\ &其中\alpha[i]为第i个质因子(不包含1)次数\\\\ \mu(6)=1{~} &\mu(7)=-1{~} \mu(8)=0 \end{aligned} $$
2 性质
$$ \begin{aligned} s(n) &= \sum_{d,d为n的所有约数} \mu(d) \\\\ &= 1 (当n=1)\\\\ &= 0 (当n>0)\\\\ s(6) &= \mu(1) + \mu(2) + \mu(3) + \mu(6)\\\\ &= 1 - 1 - 1 + 1 \end{aligned} $$
$$ \begin{aligned} n &= p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\\\\ \alpha &= p_1^{\beta_1}p_2^{\beta_2}p_3^{\beta_3}{~}0 \le \beta_i \le \alpha_i\\\\ \end{aligned} $$
证明
$$ \begin{aligned} \beta_i &\geq 2时 乘积=0 \\\\ \mu(d) &= (-1)^m (m代表\beta_i 中1的个数)\\\\ s(n) &= C_k^0 * (-1)^0 + C_k^1 * (-1)^1+…+c_k^k * (-1)^k\\\\ (a+b)^k &= C_k^0 * a^k * b^0 + C_k^1 * a^{k-1}*b^1+…+c_k^k a^0 * b^k\\\\ 则s(n) &= (1-1)^k = 0^k = 0\\\\ \end{aligned} $$
3 莫比乌斯反演
$$ \begin{aligned} F(n) &= \sum_{d} f(\alpha) \\\\ f(n) &= \sum_{d} \mu(d) F(\frac{\mu}{d})\\\\ 其中 d &为 n的约数 \end{aligned} $$
证明
$$
\begin{aligned}
\sum_{d} \mu(d) F(\frac{\mu}{d}) & = \sum_{d|n} \mu(d)\sum_{i|\frac{n}{d}} f(i) \\\\
&其中i为\frac{\mu}{d}的约数 \\\\
for … &d \\\\
for .&.. i \\\\
& sum += \mu(d)f(i)\\\\
& = \mu(d_1) * (f(i_1)+f(i_2)+…) 其中i_j为d_1的约数\\\\
& = \mu(d_2) * (f(i_1)+f(i_2)+…) 其中i_j为d_2的约数\\\\
想交换&循环变量顺序\\\\
则需要 &d|n {~~~} i|\frac{n}{d} {~} <=> id|n <=> d|\frac{n}{i}\\\\
原式 &= \sum_{i|n} f(i) \sum_{d|\frac{n}{i}} \mu(d)\\\\
(性质2) &= \sum_{i|n} f(i) s(\frac{n}{i})\\\\
(性质2,将i=n与其他项分开) &= \sum_{i|n,i!=n} f(i) * s(\frac{n}{i}) + f(n) * s(\frac{n}{n})\\\\
(性质2) &= 0 + f(n) * 1\\\\
&= f(n) \\\\
\end{aligned}
$$
倍数证明 28:30 未完待续
blablabla