卷積與莫比烏斯反演

目錄

卷積與莫比烏斯反演

0前言

? ? ? ??0.1前置技能

? ? ? ??0.2問題的引入

1.簡單定義

? ? ? ??1.1數論函數的定義

? ? ? ??1.2卷積的定義

? ? ? ??1.3反演的基本形式

2.1莫比烏斯反演

3.1例題：【luogu-P2257 YY的GCD】

題目大意：

solution1

solution2

---

0.前言

莫比烏斯反演是數論數學中很重要的內容，可以用于解決很多組合數學的問題。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 來源——百度百科

0.1前置技能

?

• 初一數學水平。
• 對卷積、莫比烏斯函數有簡單了解。

0.2問題的引入

OI競賽中，經常遇到這樣一類數學問題：

顯然，暴力的時間復雜度是的，顯然這個復雜度是我們無法接受的。

然而，倘若我們使用莫比烏斯反演，就能夠大大優化其時間復雜度。

?

1.簡單定義

?

1.1數論函數的定義

若函數是正整數域內的函數，則稱為數論函數。

對于一個數論函數，對于任意互質的正整數，滿足，則稱?是積性函數。

對于一個數論函數，對于任意的正整數，滿足，則稱?是完全積性函數。

1.2卷積的定義

有兩個數論函數,則他們的卷積：

易得：若兩個數論函數是積性的，那么卷積?也是積性的。

設? ? ?? ? ?

有以下一些常用的函數：

?

?

• 元函數：
• 恒等函數：
• 單位函數：
• 歐拉函數：? ? 表示??? 中與n互質的數的個數。
• 莫比烏斯函數：
• 約數和函數：? ? 表示n的正約數和。?
• 約數個數函數：??? ?表示n的正約數個數。 ‘

容易發現如下性質：

?

• 對于任意數論函數? ?? ? 這是莫比烏斯反演的核心公式。
• 對于任意數論函數。

1.3容斥

我們定義一個函數,再通過定義函數，使得：

我們可以從?函數的值?反推出函數的值。

倘若我們能快速計算函數的值，那么就可以求得?。

事實上，這與反演的思想有異曲同工之妙。

?

?2.1莫比烏斯反演

在莫比烏斯反演中，我們需要快速求出：

因此??

除此之外，還有? ????

在能夠快速求得函數的情況下，我們就可以很容易地得出函數的值。

這就是莫比烏斯反演了。

?

3.1例題：【luogu-P2257 YY的GCD】

?

題目大意：

給定。

求且??為質數的??有多少對。

? ??

?

solution1

這一個簡單的不使用反演的解法。（事實上就是寫出了反演省略的步驟）

顯然：

把K提出來：

設? ?

直接數論分塊即可。

?

solution2

這是一個運用反演知識的解法。

設??表示滿足???且?? 的? 的對數。

設? 表示滿足? 且??的? 的對數。

那么：

? 且??

使用莫比烏斯反演，即得：

便可以得到solution1中的式子，直接數論分塊做。

?

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e7+50; int pnum=0; bool vis[MAXN]; ll mu[MAXN],Prime[MAXN],sum[MAXN],g[MAXN]; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } void init(int n) {vis[1]=mu[1]=1;for (int i=2;i<=n;i++){if (!vis[i]) { mu[i]=-1; Prime[++pnum]=i; }for (int j=1;j<=pnum&&Prime[j]*i<=n;j++){vis[Prime[j]*i]=1;if (!(i%Prime[j])) break;mu[Prime[j]*i]=-mu[i];}}for (int i=1;i<=n;i++)for (int j=1;j<=pnum&&Prime[j]*i<=n;j++) g[Prime[j]*i]+=mu[i]; for (int i=1;i<=n;i++) sum[i]=sum[i-1]+g[i]; } int main() {init(1e7);int Case=read();while (Case--){ll n=read(),m=read(),ans=0;if (n>m) swap(n,m);for (ll l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);} printf("%lld\n",ans);}return 0; }

時間復雜度大概是???。

總結

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

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