問題引入：

給定整數 N 和 M。求滿足??且??為質數的點對??的個數。

數據范圍：

?

接下來會見到以下內容：

• 莫比烏斯函數
• 莫比烏斯函數的線性篩
• 迪利克雷卷積介紹
• 莫比烏斯反演
• 整除分塊
• 杜教篩介紹

?

莫比烏斯函數：

這里 else 是指：n有大于1的平方因子的情況，如，4、9、16等。

?

莫比烏斯函數的線性篩：

其實，莫比烏斯函數線性篩與普通的線性篩基本相同，只是多了一個 mu[MAXN] 數組罷了。

int prime[MAXN], prime_tot;//prime[MAXN]用于保存質數，prime_tot是質數的個數; bool prime_tag[MAXN];//標記是否為質數，false表示是質數，true表示合數; int mu[MAXN];//保存n的莫比烏斯函數值; void pre_calc(int lim){mu[1] = 1;for (int i = 2; i <= lim; ++i) {if(!prime_tag[i]) {prime[++prime_tot] = i;mu[i] = -1;//質數的莫比烏斯函數值必為-1; }for (int j = 1; j <= prime_tot; ++j) {if(i * prime[j] > lim)break;prime_tag[i * prime[j] ] = true;//質數的倍數必是合數 if(i % prime[j] == 0) {//如果 i能被質數整除 說明 i中必有同一個質數因子//那么 i*prime[j] 就必有平方因子 mu[i * prime[j] ] = 0;break;}else {mu[i * prime[j] ] = -mu[i];}}} }

?

狄利克雷卷積介紹：

狄利克雷卷積是函數之間的運算。

狄利克雷卷積：。

積性函數：對于任意互質的整數 a和b 有性質?的函數。

完全積性函數：對于任意整數 a和b 有性質?的函數。

?

證明：

設 n 不同的因子的個數為 k，則有

由二項式定理展開，得

令 x = -1，y = 1，代入得

即

?

下面是一些常見的積性函數：

①歐拉函數?

歐拉函數是求??的質數的個數。

?

②莫比烏斯函數?

本節所講函數。

?

③單位函數?

n 是多少就是多少。

?

④不變函數?

恒等于 1。

?

⑤冪函數?

易知，。

?

⑥因子個數函數?（注意，這里是指不變函數相乘）

?

⑦因子和函數?

?

⑧因子函數?

?

⑨狄利克雷卷積單位元?

?

其中，①②⑨是比較重要的函數。

（注意：這里的??是指做卷積）

?

莫比烏斯反演：

公式一：

?

公式二：

（數論千萬條，反演第一條。反演不會做，隊友兩行淚。）

兩條公式的差別：一條是印數關系，一條是倍數關系。

?

公式一證明：

?

是不是特別簡單？

可是，為什么??會消去？

答案是，不變函數是莫比烏斯函數的乘法逆元。

還不知道什么是乘法逆元的，可以先去學習一下。

?

公式二證明：

令?，則

?

想一想，為什么第三條式子可以變為第四條式子呢？

因為，當且僅當 (nk|t) 成立的時候，才會對求和有貢獻。

?

那么，第四條式子又是怎么去到第五條式子的呢？

仔細看看，?是不是成立？那么，也就出來了。

?

最后，根據狄利克雷卷積單位元的性質，當且僅當 t?= n?，即??時才會有貢獻，證畢。

?

回歸問題：

?

?

求?，p是質數。

?

定義，

?

那么，?且有?.。

?

下面開始反演：

?

到這里，復雜度已經降下來一些了，那么怎么解決左邊的這一塊呢？

?

我們預處理一個?。

for (int i = 1; i <= prime_tot; ++i) {for (int j = 1; prime[i] * j <= lim; ++j) {sum[prime[i] * j] += mu[j];} }

?

最終，?。

?

整除分塊：

?約有??個可能值。

如，N = 25，k = 1，2，3，4，5，6，7-8，9-12，13-25時，?共有 9 個互不相同的值。

快速計算的方法：

for (int l = 1, r; i <= N; l = r + 1) {r = N / (N / l);ans += (r - l + 1) * (N / l); }

?

杜教篩：

有些題目要用到前綴和，但是數據范圍會很大，這是要用到杜教篩。

例如，求?

?

定義：

int mu_sum[MAXN]; unordered_map<long long, int> mp; int mu_calc (long long n) {if (n < lim) return mu_sum[n];if (mp.count(n)) return mp[n];int ret = 1;for (long long l = 2, r; l <= n; l = r +1) {r = n / (n / l);ret -= (r - l + 1) * mu_calc(n / l);}return mp[n] = ret; }

當然，杜教篩還可以應用到更多地方。

?

本文章學習來自：

【算法講堂】【電子科技大學】【ACM】莫比烏斯反演

?

題目練習：

待補充。。

總結

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

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