算法学习-莫比乌斯反演

写在前面

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

莫比乌斯反演公式

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

基础知识

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

莫比乌斯反演的证明

• 可以从后向前证明.
• 已知 $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)$$
  然后的1步让我很头疼, 要把 $f(k)$ 提出来, 统计 $f(k)$ 所乘的 $mu(d)$的和.
  仔细视察, $k$ 的取值范围就是 $n$ 的所有因子. 如果 $f(k)$ 要和 $mu(d)$ 相乘, 那末满足的关系是 $k|frac n d$, 也就是 $k*m=frac n d$, 变换1下情势就得到 $d*m=frac n k$, 即 $d|frac n k$. 也就是 f(k) 生活不易，码农辛苦
  如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠