【目錄】
- 莫比烏斯函數
- 莫比烏斯反演
莫比烏斯函數
定義
莫比烏斯函數\(\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)\)可以在線性時間內求出。