莫比烏斯反演公式證明，莫比烏斯函數與莫比烏斯反演

【目錄】

• 莫比烏斯函數
• 莫比烏斯反演

---

莫比烏斯函數

定義

莫比烏斯函數\(\mu(n)\)，當\(n=1\)時，\(\mu(n)=1\)；當\(n>1\)時，設\(n\)的唯一分解式為\(n=p_1^{c_1}\cdots p_k^{c_k}\)，則\(\mu(n)\)定義為
\[\mu(n)= \begin{cases} (-1)^k,c_1=c_2=\cdots=c_k=1 \\ 0, \exists\, c_i>1(1\leq i\leq k)\\ \end{cases}\]

性質

• \(\sum\limits_{d|n}\mu(d)=[n=1]\)
  注：約定方括號[]中為一個命題，其結果為\(1\)（該命題為真），或為\(0\)（該命題為假）。例如\([p為質數]\)=\(\begin{cases} 1,p是質數 \\ 0,p不是質數 \\ \end{cases}\)
  證明：\(n=1\)時，顯然成立；現設\(n>1\)，\(n\)的唯一分解式為\(n=p_1^{c_1}\cdots p_k^{c_k}\)，則
  \[\begin{aligned} \sum\limits_{d|n}\mu(d) =&\mu(1)+\mu(p_1)+\cdots+\mu(p_k)+\mu(p_1p_2)\\ &+\cdots +\mu(p_{k-1}p_k)+\cdots+\mu(p_1\cdots p_k)\\ =&1+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+\cdots+\binom{k}{k}(-1)^k\\ =&(1-1)^k=0 \end{aligned}\]
• \(\varphi(n)=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}\)
  證明：
  因為\(\varphi(n)=n\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_k}\right)\)，其中\(n=p_1^{c_1}\cdots p_k^{c_k}\)是\(n\)的標準分解式，利用\(\mu(n)\)，可得\(\varphi(n)=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}\)。

---

莫比烏斯反演

觀察這兩個等式
\[\begin{aligned} n&=\sum\limits_{d|n}\varphi(d)=\sum\limits_{d|n}\varphi\left(\dfrac{n}{d}\right)\\ \varphi(n)&=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}=\sum\limits_{d|n}\mu\left(\dfrac{n}{d}\right)d\\ \end{aligned}\]
考慮將其推廣至一般情況

莫比烏斯變換

對于數論函數\(f(n),g(n)\)，若
\[f(n)=\sum\limits_{d|n}g(d)=\sum\limits_{d|n}g\left(\dfrac{n}{d}\right)\]
則稱\(f(n)\)為\(g(n)\)的莫比烏斯變換，而\(g(n)\)為\(f(n)\)的莫比烏斯逆變換。

反演公式

若有兩個數論函數\(f(n),g(n)\)滿足
\[ f(n)=\sum\limits_{d|n}g(d)\qquad \qquad (1)\]
則有
\[ g(n)=\sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right) \qquad \qquad (2)\]
反過來，若滿足\((2)\)，則\((1)\)也成立。
證明： 若\(f(n),g(n)\)滿足\((1)\)，則
\[\begin{aligned} \sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right)&=\sum\limits_{d|n}\mu(d)\sum\limits_{d'|\frac{n}{d}}g(d')\\ &=\sum\limits_{dd'|n}\mu(d)g(d')\\ &=\sum\limits_{d'|n}\sum\limits_{d|\frac{n}{d'}}\mu(d)g(d')\\ &=\sum\limits_{d'|n}g(d')\sum\limits_{d|\frac{n}{d'}}\mu(d)\\ &=g(n)\\ \end{aligned}\]
反過來，設\(f(n),g(n)\)滿足\((2)\)，同法可證
\[\begin{aligned} \sum\limits_{d|n}g(d)&=\sum\limits_{d|n}g\left(\dfrac{n}{d}\right)\\ &=\sum\limits_{d|n}\sum\limits_{d'|\frac{n}{d}}\mu\left(\dfrac{n}{dd'}\right)f(d')\\ &=\sum\limits_{dd'|n}\mu\left(\dfrac{n}{dd'}\right)f(d')\\ &=\sum\limits_{d'|n}f(d')\sum\limits_{d|\frac{n}{d'}}\mu\left(\dfrac{n}{dd'}\right)\\ &=f(n)\\ \end{aligned}\]

在OI中的應用

通常，在OI競賽中，應用莫比烏斯反演的關鍵在于構造如下的式子
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))\]
其中\(f(n)\)是一個積性函數。
構造數論函數\(g(n)\)滿足\(f(n)=\sum\limits_{d|n}g(d)\)，
由莫比烏斯反演公式得\(g(n)=\sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right)\)。
化簡原式
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}g(d)\]
因為\(d|\gcd(i,j)\Leftrightarrow d|i,d|j\)，所以\(d\)必須是\(i,j\)的約數
考慮對每個\(d\)，枚舉\(d\)的倍數，接著化簡
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))&=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{d|i}^n \sum\limits_{d|j}^mg(d)\\ &=\sum\limits_{d=1}^{\min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor g(d) \end{aligned}\]
這樣只需要枚舉\(d\)，就能求出\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f(\gcd(i,j))\)，時間復雜度為\(O(n)\)。
考慮\(\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\)可以使用數論分塊，再預處理一下\(g(n)\)的前綴和，時間復雜度降至\(O(\sqrt n)\)。
至于\(g(n)\)的計算，因為\(g(n)=\sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right)\)，而\(f(n),\mu(n)\)為積性函數，所以\(g(n)\)也是積性函數。參考這篇博客，\(g(n)\)可以在線性時間內求出。