论莫比乌斯函数及其应用

发布于：2022-12-03 ⋅ 阅读:(1039) ⋅ 点赞:(0)

引言：

莫比乌斯函数是为解决容斥原理问题而定义的数论函数，但其功能远远超出容斥原理的范围，可以通过由该函数衍生出的莫比乌斯反演化简很多复杂的式子，降低运算复杂度。但莫比乌斯反演需要一定的数学知识和推导能力，于是我在此介绍莫比乌斯函数及其应用。

摘要：

莫比乌斯函数与其他数论函数以狄利克雷卷积为纽带相互联系相互转化，构成莫比乌斯反演算法，可实现快速计算复杂和式。

正文：

莫比乌斯函数形式化的定义是：

  N=\prod\limits_{i=1}^m p_i^{c_i} 

\mu(N)=\begin{cases}0&\exists x\in[1,m],c_x\ge 2\\1&2\mid m,\forall x\in[1,m],c_x=1\\-1&2 \nmid m,\forall x\in[1,m],c_x=1\end{cases}

通俗来讲，就是若含有平方因子，函数值为零；否则若有偶数个因子值为一，奇数为负一。这显然是一个积性函数。既然是积性函数，在互质时便可由已知函数值的集合导出位置的函数值，不断将位置集合的元素纳出已知集合，实现求解；而在非互质时便可由定义直接将函数值赋为0。结合线性筛法，可以在线性时间内计算 1~N 之间的所有函数值。多数数论函数都满足积性函数的性质，且在非互质时可使用特殊的方法快速求解，因此使用线性筛成为了计算许多数论函数值的手段。另外，如果只求单点函数值，直接分解质因数就行。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int v[N],p[N];
int mu[N],cnt;
inline void isprime(int maxV)	{
	mu[1]=1;
	for(int i=2;i<=maxV;i++)	{
		if(!v[i])
			v[i]=i,p[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt;j++)	{
			if(p[j]>v[i]||p[j]>maxV/i) break;
			v[i*p[j]]=p[j];
			if(i%p[j]) mu[i*p[j]]=-mu[i];
			else mu[i*p[j]]=0;
		}
	}
	for(int i=1;i<=maxV;i++)
		printf("%d\n",mu[i]);
	return;
}
int main(void)
{
	isprime(1e3+7);
	return 0;
}

当然只有这些是远远不够的，反演才是重中之重。首先介绍一个概念：狄利克雷卷积。其形式化的内容是：如果定义在自然数上的函数 f(N) 满足

 h(N)=\sum\limits_{d\mid N} f(d) g(\frac{N}{d})

则可以推出

f(N)=\sum\limits_{d\mid N} h(d) \mu(\frac{N}{d}) g(\frac{N}{d})

由此可以得到一些常用结论：

1 * \mu=e        \mu * id=\phi        1 * id=\sigma        1*1=d

1*d=\phi        1*\phi=id        d*\phi=\sigma

这就意味着莫比乌斯函数与其他数论函数，以及其他数论函数之间都可以以狄利克雷卷积为纽带相互转化。而迪利克雷卷积可实现将根号级复杂度向常数级的转变，这就是莫比乌斯反演可降低计算复杂度的原因所在。仔细考虑可以发现卷积满足交换结合律。

例题：

解析： 

题目要求 \gcd(i,j)=d，显然可以转化为  gcd(i/d,j/d)=1。这不就是 e(N) 函数吗？于是根据这个思路，进行反演。根据卷积公式，可以得到：

\sum\limits_{d\mid N} 1(d) e(\frac{N}{d})=e(\frac{N}{N})=1=1(N)

e(N)=\sum\limits_{d\mid N} 1(d) \mu(\frac{N}{d})1(\frac{N}{d})=\sum\limits_{d\mid N}\mu(d)

所以带入可得：

\sum\limits_{i=1}^n \sum\limits_{j=1}^m e(\gcd(i/d,j/d))=\sum\limits_{i=1}^{\lfloor n/d \rfloor} \sum\limits_{j=1}^{\lfloor m/d\rfloor } e(\gcd(i,j))=\sum\limits_{i=1}^{\lfloor n/d \rfloor} \sum\limits_{j=1}^{\lfloor m/d\rfloor } \sum\limits_{k\mid \gcd(i,j)} \mu(k)=\sum\limits_{k=1}^{min(n,m)} \mu(k) \sum\limits_{i=1}^{\lfloor n/dk \rfloor} \sum\limits_{j=1}^{\lfloor m/dk\rfloor } 1=\sum\limits_{k=1}^{min(n,m)} \mu(k) \lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor

这已经是线性的了，但并不是最优复杂度，可以使用数论分块，将复杂度降到根号级。其大体思路是这样的：

f(x)=\frac{k}{x}      g(x)=\lfloor \frac{k}{\lfloor k/x \rfloor}\rfloor

 \because f^{'}(x)=-\frac{k}{x^2}<0        g(x) \geq \lfloor \frac{k}{k/x} \rfloor=x

\therefore \lfloor k/g(x) \rfloor \le \lfloor k/x \rfloor

\because \lfloor\frac{k}{g(x)}\rfloor \ge \lfloor \frac{k}{k/\lfloor k/x \rfloor} \rfloor=\lfloor \frac{k}{x} \rfloor

\therefore \lfloor \frac{k}{g(x)} \rfloor =\lfloor \frac{k}{x} \rfloor

\therefore \forall i,j\in[x,\lfloor \frac{k}{g(x)} \rfloor] ,\lfloor \frac{k}{i}\rfloor=\lfloor \frac{k}{j}\rfloor

通过推导，我们发现经常有连续的一大串数字中， \lfloor k/x \rfloor 都相等。我们可以利用这一点，不枚举 T，对每一段 \lfloor k/x \rfloor 相等的数字都套用等差数列求和公式，现在分析复杂度。若 i \le \sqrt k ，显然  \lfloor k/i \rfloor 只有 \sqrt k 个不同的值。若 i\ge \sqrt k ，\lfloor k/i \rfloor \le \sqrt k，还是只有 \sqrt k 个不同的值。所以数论分块复杂度是 O(\sqrt N)。现在就可以愉快的解决这道题了。由于狄利克雷卷积中存在着 \lfloor n/d \rfloor  项，所以许多莫比乌斯反演的结果都可通过数论分块进一步降低复杂度。

例题：

解析： 

\sum\limits_{i=1}^n \sum\limits_{j=1}^m lcm(i,j)=\sum\limits_{i=1}^n \sum\limits_{j=1}^m \frac{ij}{\gcd(i,j)}=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=d] \frac{ij}{d}=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{n/d} \sum\limits_{j=1}^{m/d} e(\gcd(i,j)) \frac{ij}{d}=\sum\limits_{d=1}^{min(n,m)}d\sum\limits_{i=1}^{n/d} \sum\limits_{j=1}^{m/d} \sum\limits_{e \mid gcd(i,j)} \mu(e) ij=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{e=1}^{min(n/d,m/d)} \mu(e)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}ij[e\mid \gcd(i,j)]

 这里不妨设 i=es,j=et。原柿就可以写成：

\sum\limits_{d=1}^{min(n,m)} d\sum\limits_{e=1}^{min(n/d,m/d)} \mu(e)\sum\limits_{es=1}^{n/d}\sum\limits_{et=1}^{m/d} e^2st=\sum\limits_{d=1}^{min(n,m)}d \sum\limits_{e=1}^{min(n/d,m/d)} e^2\mu(e)(\sum\limits_{s=1}^{n/de} s)(\sum\limits_{t=1}^{m/de} t)

s,t 可以用等差数列求和直接求出来，这里就设 sum(n)=n(n+1)/2 。原柿就能写成：

\sum\limits_{d=1}^{min(n,m)}d \sum\limits_{e=1}^{min(n/d,m/d)} e^2\mu(e)\cdot sum(\frac{n}{de})sum(\frac{m}{de})

令 T=de ，还能继续化简：

\sum\limits_{T=1}^{min(n,m)} sum(\frac{n}{T})sum(\frac{m}{T}) T \sum\limits_{f\mid T} f\mu(f)

为了更方便的处理，我们构造一个函数：

 f(x)=\sum\limits_{t\mid x} t\mu(t) 

显然这是一个积性函数，可以通过线性筛来求解。这启示我们不仅 \phi(n),\mu(n),\sigma(n) 等数论函数可以结合线性筛，往往自己构造的函数也可以。接下来说一下求解的具体方法。

f(p)=1\cdot \mu(1)+p\cdot mu(p)=1-p

f(xp)=f(x)f(p)        (p\nmid x)

f(xp)=f(p)        (p\mid x)

结合上面三个式子，就可以使用线性筛了。同样的使用数论分块，愉快通过。贴个代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=20101009,N=10000005;
int f[N],pri[N],is[N],s[N];
int n,m,tot,ans,div2;
int qm(int x) {return x>=mod?x-mod:x;}
void init() {
    f[1]=1;
    for(int i=2;i<=n;++i) {
        if(!is[i]) pri[++tot]=i,f[i]=qm(mod+1-i);
        for(int j=1;j<=tot&&i*pri[j]<=n;++j) {
            int k=i*pri[j]; is[k]=1;
            if(i%pri[j]) f[k]=1LL*f[i]*f[pri[j]]%mod;
            else {f[k]=f[i];break;}
        }
    }
    for(int i=1;i<=n;++i) f[i]=qm(f[i-1]+1LL*f[i]*i%mod);
    for(int i=1;i<=m;++i) s[i]=qm(s[i-1]+i);
}
int main()
{
   	scanf("%d%d",&n,&m);
   	if(n>m) swap(n,m);
   	init();
   	for(int i=1,j;i<=n;i=j+1) {
   		j=min(n/(n/i),m/(m/i));
   		ans=qm(ans+1LL*qm(f[j]-f[i-1]+mod)*s[n/i]%mod*s[m/i]%mod);
   	}
   	printf("%d\n",ans);
    return 0;
}

例题：

解析：

还是这个柿子：

\sum\limits_{d\mid N} 1(d) e(\frac{N}{d})=e(\frac{N}{N})=1=1(N)

e(N)=\sum\limits_{d\mid N} 1(d) \mu(\frac{N}{d})1(\frac{N}{d})=\sum\limits_{d\mid N}\mu(d)

带入可得：

\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n \gcd(i,j)=\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n \sum\limits_{d\mid \gcd(i,j)} d \cdot\[gcd(i,j)=1] \cdot 1(\frac{\gcd(i,j)}{d}) \cdot \mu(d)=\sum\limits_{d=1}^n d\cdot \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}} e(\gcd(i,j))=\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\frac{n}{d}} \sum\limits_{j=1}^{\frac{n}{d}} \sum\limits_{e\mid \gcd(i,j)} \mu(e)=\sum\limits_{d=1}^n d \sum\limits_{e=1}^n \mu(e) \lfloor\frac{n}{d e}\rfloor^2

做到这里已经把 O(N^2\log N) 优化到了 O(N^2)。继续推：

令 T=de

\sum\limits_{T=1}^n \sum\limits_{k\mid T} k\mu({\frac{T}{k}})\lfloor\frac{n}{T}\rfloor^2

根据之前的结论：id * \mu=\phi  原柿就能写成：

\sum\limits_{T=1}^N \phi(T) \lfloor \frac{n}{T}\rfloor^2

此外上式并非输出结果。考虑所有 i=j 的情况，我们恰好多算了一个等差数列。而 i<j 的情况与 i>j 的情况两两对称，仍需除以二。设原柿= A，结果就是 \frac{A-\frac{N(N+1)}{2}}{2}。

贴个代码（第一篇题解）：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e6+5;
ll p[N],n;ll phi[N];bool notp[N];
void seive(ll n){
    phi[1] = 1;
    for(ll i=2;i<=n;++i) {
        if(!notp[i]) p[++p[0]] = i, phi[i] = i-1;
        for(ll j=1;j<=p[0] && i*p[j]<=n;++j) {
            notp[i*p[j]] = 1;
            if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
            phi[i*p[j]] = phi[i]*(p[j]-1);
        }
    }
    for(ll i=1;i<=n;++i) phi[i] += phi[i-1];
}
ll cal(ll n,ll m){
    ll ans = 0;ll r;
    for(ll i=1;i<=n;i=r+1) {
        r = min(n/(n/i), m/(m/i));
        ans += (phi[r]-phi[i-1]) * (n/i) * (m/i);
    }
    return ans;
}
int main() {
    scanf("%lld",&n);
    seive(n);
    printf("%lld\n",(cal(n,n)-n*(n+1)/2)/2);
}

还有一道非常相似的题目：

解析： 

\sum\limits_{i=1}^n \sum\limits_{j=1}^m 2\gcd(i,j)-1=2\sum\limits_{i=1}^n\sum\limits_{j=1}^m \gcd(i,j) - nm

这就又回到了上一题。

例题：

解析： 

还是，先列暴力柿子，然后反演优化：

\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j) \in prime]=\sum\limits_{p=1}^{min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=p]     

这里是不是和第一道题有点相似？一样的套路：

\sum\limits_{k=1}^{min(n,m)}\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}e(\gcd(i,j))=\sum\limits_{k=1}^{min(n,m)}\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}\sum\limits_{d\mid gcd(i,j)} \mu(d)=\sum\limits_{k=1}^{min(n,m)}\sum\limits_{d=1}^{min(n,m)} \mu(d) \lfloor \frac{n}{dk}\rfloor \lfloor \frac{m}{dk} \rfloor

与上一题不同的是：这里多了一层循环。这样复杂度是 O(\frac{n\sqrt n}{\ln n})。还是不行。。这里就需要一点小技巧了，令 T=dk，改写原柿子：

\sum\limits_{k=1}^{min(n,m)}\sum\limits_{d=1}^{min(n,m)} \mu(\frac{T}{k}) \lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T} \rfloor=\sum\limits_{T=1}^{min(n,m)}\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T}\rfloor \sum\limits_{k\mid T,k\in prime} \mu(\frac{T}{k})

看似没啥变化，但后面 k 的循环可以预处理。设质数有 cnt 个，复杂度就是：

O(\frac{cnt}{2}+\frac{cnt}{3}+\frac{cnt}{5}..)<O(cnt \ln cnt)=O(\frac{n}{\ln n}\ln \frac{n}{\ln n})=O(\frac{n}{\ln n}(\ln n-\ln\ln n))<O(n)

在复杂度估计中除质数密度估计还涉及调和级数求和的知识，其复杂度等同于对数，此处不赘述了。这样就解决了这个问题。贴个代码（第一篇题解）：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL mu[10000010];int flag[10000010],prime[10000010],cnt,f[10000010],sum[10000010];
void sieve() {
    mu[1]=1;
    for (int i=2;i<=10000000;i++) {
        if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=1;i<=cnt;i++)
        for (int j=1;prime[i]*j<=10000000;j++)
            f[j*prime[i]]+=mu[j];
    for (int i=1;i<=10000000;i++)
        sum[i]=sum[i-1]+f[i];
}
LL solve(int a,int b) {
    LL ans=0;
    if (a>b) swap(a,b);
    for (int l=1,r=0;l<=a;l=r+1) {
        r=min(a/(a/l),b/(b/l));
        ans+=(LL)(sum[r]-sum[l-1])*(LL)(a/l)*(LL)(b/l);
    }
    return ans;
}
int main() {
    sieve();
    int n,m,T;scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        if (n>m) swap(n,m);
        printf("%lld\n",solve(n,m));
    }
}

参考文献：李煜东《算法竞赛进阶指南》，洛谷题库

李煜东在书中仅介绍了莫比乌斯函数的定义，并未涉及莫比乌斯反演、狄利克雷卷积以及数论函数的知识。文中例题来自洛谷题库，代码无特殊说明均为笔试所写。

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布