算法学习-莫比乌斯反演

写在前面

• 必须把更多的精力放在文化课上了, 所以这段时间的学习和数学相关的比较多, 希望可以对文化课有帮助.

莫比乌斯反演公式

• $$g(n)=\sum_{d|n}f(d)\Rightarrow f(n)=\sum_{d|n}\mu(d)g(\frac n d)$$

基础知识

• $\mu$函数
  $$f(n) = \begin{cases} 1, & n=1 \(-1)^k, & n=p_1*p_2*...*p_k \0, &n=others \end{cases}$$
• $\mu$ 函数是积性函数, 因为当 n 是质数时 $\mu(n)=(-1)^1=-1$, 所以可以通过筛法求出 $\mu$ 函数.

mu[1] = 1;
for(i = 2; i <= n; i++) {
    if(!vis[i]) {
        prime[++c] = i;
        mu[i] = -1;
    }
    for(j = 1; prime[j] * i <= n; j++) {
        vis[prime[j] * i] = 1;
        if(i % prime[j] == 0) {
            mu[prime[j] * i] = 0;
            break;
        }
        mu[prime[j] * i] = -mu[i];
    }
}

莫比乌斯反演的证明

• 可以从后向前证明.
• 已知 $g(n)=\sum_{d|n}f(d)$
• 求证 $f(n)=\sum_{d|n}\mu(d)g(\frac n d)$
• 证明
  $$f(n)=\sum_{d|n}\mu(d)g(\frac n d)=\sum_{d|n}\mu(d)\sum_{k |\frac n d}f(k)=\sum_{d|n}\sum_{k|\frac n d}f(k)*\mu(d)$$
  然后的一步让我很头疼, 要把 $f(k)$ 提出来, 统计 $f(k)$ 所乘的 $\mu(d)$的和.
  仔细观察, $k$ 的取值范围就是 $n$ 的所有因子. 如果 $f(k)$ 要和 $\mu(d)$ 相乘, 那么满足的关系是 $k|\frac n d$, 也就是 $k*m=\frac n d$, 变换一下形式就得到 $d*m=\frac n k$, 即 $d|\frac n k$. 也就是 $f(k)$ 要和所有 $d|\frac n k$ 的 $d$ 相乘.
  用这个结论继续化简刚才的式子, 得到下面
  $$f(n)=\sum_{d|n}\sum_{k|\frac n d}f(k)*\mu(d)=\sum_{k|n}f(k)\sum_{d|\frac n k}\mu(d)$$
  $\mu$函数有很多奇怪的性质, 比如下面这条
  $$\sum_{d|n}\mu(d)= \begin{cases} 1, & n=1 \\ 0, & n>1 \end{cases}$$
  $n=1$ 时比较显然
  $n>1$ 时将 $n$ 分解为 ${p_1}^{a1}{p_2}^{a_2}...{p_k}^{a_k}$, 而 $n$ 的所有因子中, $\mu$ 不为0的只有质因子次数都为1的因子, 其中质因数个数为 $r$ 个的有 $C_k^r$ 个. 可以得到下面的式子
  $$\sum_{d|n}\mu(d)=\sum_{i=0}^kC_k^i(-1)^i=(1+(-1))^k=0$$
  这是数学上的二项式展开. 用这个结论用到刚才推了一半的 $f(n)$
  中
  $$f(n)=\sum_{k|n}f(k)\sum_{d|\frac n k}\mu(d)$$
  发现除非 $n=k$ 这时 $\sum_{d|\frac n k}\mu(d)=1$, 否则为0.
  最后就得到 $f(n)=f(n)$ 说明命题是正确的.

后记

• 准备做几道题应用应用.