寫在前面

• 必須把更多的精力放在文化課上了, 所以這段時間的學習和數學相干的比較多, 希望可以對文化課有幫助.

莫比烏斯反演公式

• g(n)=∑d|nf(d)?f(n)=∑d|nμ(d)g(nd)
  $$g(n)=sum_{d|n}f(d)Rightarrow f(n)=sum_{d|n}mu(d)g(frac n d)$$

基礎知識

• μ$mu$函數
  
  f(n)=???1,(?1)k,0,n=1n=p1?p2?...?pkn=others
  $$f(n) = egin{cases} 1, & n=1 (⑴)^k, & n=p_1*p_2*...*p_k 0, &n=others end{cases}$$
• μ$mu$ 函數是積性函數, 由于當 n 是質數時 μ(n)=(?1)1=?1$mu(n)=(⑴)^1=⑴$, 所以可以通過篩法求出 μ$mu$ 函數.

莫比烏斯反演的證明

• 可以從后向前證明.
• 已知 g(n)=∑d|nf(d)$g(n)=sum_{d|n}f(d)$
• 求證 f(n)=∑d|nμ(d)g(nd)$f(n)=sum_{d|n}mu(d)g(frac n d)$
• 證明
  
  f(n)=∑d|nμ(d)g(nd)=∑d|nμ(d)∑k|ndf(k)=∑d|n∑k|ndf(k)?μ(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)$ 提出來, 統計 f(k)$f(k)$ 所乘的 μ(d)$mu(d)$的和.
  仔細視察, k$k$ 的取值范圍就是 n$n$ 的所有因子. 如果 f(k)$f(k)$ 要和 μ(d)$mu(d)$ 相乘, 那末滿足的關系是 k|nd$k|frac n d$, 也就是 k?m=nd$k*m=frac n d$, 變換1下情勢就得到 d?m=nk$d*m=frac n k$, 即 d|nk$d|frac n k$. 也就是 f(k) 生活不易，碼農辛苦
  如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈