莫比烏斯反演

莫比烏斯反演

莫比烏斯函數\(\mu\)的定義：

\[\begin{eqnarray}\mu(i)&=&0(i含有平方因數)\\&=&(-1)^{i的因數個數}(i不含有平方因數數)\end{eqnarray}\]

\(\mu\)的性質：

積性函數（不完全）

重要公式：\(\sum_{d|n}\mu(d)=(n==1)\)

證明：

n等於1時結論顯然

否則將\(\mu(d)\)當做容斥繫數來證明

例題1：

\(\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==1)\)

\(n,m\le10^7\)

題解：

考慮原式：\(\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==1)\)

原式等於：\(\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\)

這樣在\(gcd(i,j)！=1\)時對答案無貢獻，而在它等於1是對答案貢獻唯一，符合原式

枚舉\(d\)

如果\(d\)是\(gcd(i,j)\)的因數，那麼

\(d|i\)&&\(d|j\)

對於每個d來說

在1到n的範圍中有\(\lfloor \frac{n}{d}\rfloor\)

在1到m的範圍中有\(\lfloor \frac{m}{d}\rfloor\)

相應的\(d\)作為\(gcd(i,j)\)的因數就該有\(\lfloor \frac{n}{d}\rfloor\lfloor \frac{m}{d}\rfloor\)多次

也意味著\(\mu(d)\)出現了那麼多次

那麼我們枚舉$d $

既：\(\sum_{d=1}^{n}\lfloor \frac{n}{d}\rfloor\lfloor \frac{m}{d}\rfloor\mu(d)\)

這裡d從1到n還是從1到m都無所謂

因為有若\(d\)大於\(n,m\)其中一個那麼向下取整就會變為0，既對答案無貢獻

我們發現\(\lfloor \frac{n}{d}\rfloor\)和\(\lfloor \frac{m}{d}\rfloor\)都最多只有\(\sqrt{n}\)和\(\sqrt{m}\)種取值，那麼枚舉這些取值，先預處理\(\mu\)的首碼和，就能在根號級別的時間里解決原題了。

例題2：

\(\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==prime)\)

\(n,m\le10^7\)

題解：

\[\begin{eqnarray}原式&=&\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==prime)\\枚舉gcd&=&\sum_{x\in prime}\sum_{i=1}^{\lfloor \frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}(gcd(i,j)==1)\\借用上一題公式：&=&\sum_{x\in prime}\sum_{d=1}^{n}\lfloor \frac{n}{dx}\rfloor\lfloor \frac{m}{dx}\rfloor\mu(d)\\枚舉dx &=&\sum_{k=1}^{n}\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor\sum_{x\in prime\&x|k}\mu(\frac{k}{x})\end{eqnarray}\]

線上性篩時恰好可以處理右邊的首碼和，那麼就同上一題一樣直接上就好了。

至於其他的題目，對於每次式子不斷換著東西來枚舉，枚舉到符合複雜度的形式即可√