寫在前面

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

莫比烏斯反演公式

• 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)$$

基礎(chǔ)知識

• μ$mu$函數(shù)
  
  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$ 函數(shù)是積性函數(shù), 由于當(dāng) n 是質(zhì)數(shù)時 μ(n)=(?1)1=?1$mu(n)=(⑴)^1=⑴$, 所以可以通過篩法求出 μ$mu$ 函數(shù).

莫比烏斯反演的證明

• 可以從后向前證明.
• 已知 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)$ 提出來, 統(tǒng)計 f(k)$f(k)$ 所乘的 μ(d)$mu(d)$的和.
  仔細(xì)視察, k$k$ 的取值范圍就是 n$n$ 的所有因子. 如果 f(k)$f(k)$ 要和 μ(d)$mu(d)$ 相乘, 那末滿足的關(guān)系是 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) 生活不易，碼農(nóng)辛苦
  如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈