寫在前面

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

莫比烏斯反演公式

• g(n)=∑d|nf(d)?f(n)=∑d|nμ(d)g(nd)

基礎知識

• μ函數
  f(n)=???1,(?1)k,0,n=1n=p1?p2?...?pkn=others
• μ 函數是積性函數, 因為當 n 是質數時 μ(n)=(?1)1=?1, 所以可以通過篩法求出 μ 函數.

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)=∑d|nf(d)
• 求證 f(n)=∑d|nμ(d)g(nd)
• 證明
  f(n)=∑d|nμ(d)g(nd)=∑d|nμ(d)∑k|ndf(k)=∑d|n∑k|ndf(k)?μ(d)
  然后的一步讓我很頭疼, 要把 f(k) 提出來, 統計 f(k) 所乘的 μ(d)的和.
  仔細觀察, k 的取值范圍就是 n 的所有因子. 如果 f(k) 要和 μ(d) 相乘, 那么滿足的關系是 k|nd, 也就是 k?m=nd, 變換一下形式就得到 d?m=nk, 即 d|nk. 也就是 f(k) 要和所有 d|nk 的 d 相乘.
  用這個結論繼續化簡剛才的式子, 得到下面
  f(n)=∑d|n∑k|ndf(k)?μ(d)=∑k|nf(k)∑d|nkμ(d)
  μ函數有很多奇怪的性質, 比如下面這條
  ∑d|nμ(d)={1,0,n=1n>1
  n=1 時比較顯然
  n>1 時將 n 分解為 p1a1p2a2...pkak, 而 n 的所有因子中, μ 不為0的只有質因子次數都為1的因子, 其中質因數個數為 r 個的有 Crk 個. 可以得到下面的式子
  ∑d|nμ(d)=∑i=0kCik(?1)i=(1+(?1))k=0
  這是數學上的二項式展開. 用這個結論用到剛才推了一半的 f(n)
  中
  f(n)=∑k|nf(k)∑d|nkμ(d)
  發現除非 n=k 這時 ∑d|nkμ(d)=1, 否則為0.
  最后就得到 f(n)=f(n) 說明命題是正確的.

后記

• 準備做幾道題應用應用.

總結

以上是生活随笔為你收集整理的算法学习-莫比乌斯反演的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。