淺談莫比烏斯反演的常見套路

部落格園已挂，表示不想修了，直接來這裡看吧

整理一下，不然再過三天就又忘了。

莫比烏斯反演的套路

emmm，因為我做過的題太少了，是以可能非常不全。

以下的式子都是用\(\sum_{d \ | n} \mu(d) = [n = 1]\)推出來的，想看"正規"形式的可以參考這裡

如果不做特殊說明的話，\(\frac{n}{k}\)預設為下取整，保證\(n < m\)

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

這類應該是最基礎的問題

\begin{aligned}

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

&\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} [gcd(i, j)]\

&\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} \sum_{d \ | gcd(i, j)} \mu(d)\

&\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} \sum_{d \ | i} \sum_{d \ | j}\mu(d)\

&\sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{k}} \sum_{d \ | i} \sum_{j = 1}^{\frac{m}{k}}\sum_{d \ | j} 1\

&\sum_{d = 1}^n \mu(d) \frac{n}{kd} \frac{m}{kd}\

\end{aligned}

然後直接對後面的數論分塊就行了

題目

BZOJ1101: [POI2007]Zap

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

按照套路，枚舉\(gcd\)

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

&\text{後面的一坨直接按照第一種套路推，最終會得到}\

&\sum_{d = 1}^n \sum_{k=1}^n \mu(k) \frac{n}{kd} \frac{m}{kd}\

&\text{設\(T = kd\)}\

&\sum_{T = 1}^n \frac{n}{T} \frac{m}{T} \sum_{d \ | T} d \mu(\frac{T}{d})

設$g(T) = \sum_{d \ | T} d \mu(\frac{T}{d}) $

不難發現這是個嚴格的狄利克雷卷積的形式，那麼顯然\(g\)也是個積性函數，我們可以直接線性篩預處理後面的部分，數論分塊搞前面的。總的複雜度就是\(O(n + T\sqrt{n})\)

拓展

這裡題目最常見的拓展就是在\(gcd(i, j)\)外面再套一個函數，處理的政策都是一樣的，化到最後得到的基本也都是積性函數，如果不是就暴力篩，是的話線性篩。至于怎麼線性篩積性函數可以看這裡。

BZOJ4407: 于神之怒加強版

BZOJ4804: 歐拉心算

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

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

&\text{然後按照上面的套路推，可以得到下面的式子}\

&\prod_{d = 1}^n d{\sum_{k=1}{\frac{n}{d}} \mu(k) \frac{n}{kd}\frac{m}{kd}}\

&\text{設\(T= kd\)，枚舉\(T\)}\

&\prod_{T = 1}^n (\prod_{d \ | T} d{\mu(\frac{T}{d})}){\frac{n}{T} \frac{m}{T}}\

設\(g(T) = \prod_{d \ | T} d^{\mu(\frac{T}{d})}\)

到了這裡就有必要好好說說了，按照正常的套路反演出的\(g(T)\)應該是個積性函數，然而這裡并不是，但是暴力打表之後可以發現一些規律

當\(T\)為質數的幂時, 設\(T = p^q\)，那麼\(g(T) = p\)，除此之外\(g(T) = 1\)

那麼直接枚舉質數的幂次更新\(g\)，由于質數的密度大概是\(\frac{n}{\ln n}\)，而且每個質數的枚舉上界為\(\log n\)那麼總複雜度為\(O(\frac{n}{ln n}) \log n = O(n)\)

這種形式同樣有許多的拓展，最常見的也是在\(gcd\)的那裡再套上個什麼函數

比如，[SDOI2017]數字表格就是要求

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

\]

其中\(f(i)\)表示第\(i\)個斐波那契數

這種題就按照套路推，推到最後一步，如果發現\(g(T)\)不能快速計算就直接暴力枚舉因子，不然就xjb找規律。。

小結

莫比烏斯反演的一大特點就是套路性強，但是很多題還是相當有難度的，比如把某個問題轉成反演，反演轉圖論。像我這種菜雞肯定是這輩子都做不出來的qwq

參考資料

山東2017夏令營丁明朔講課

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。