莫比乌斯反演小结

摘要

复习莫比乌斯反演~

前言

OI 的数论涉及求和的部分,一般采用 暴力计算;但是当上界过大的时候就需要考虑数论求和法。

常用的技巧有前缀和、差分、组合计数、等差数列求和、矩阵快速幂等,这些技巧都建立在数学原理的基础上

如果这些仍不能解决问题,比如对于具有线性空间的嵌套求和,就要考虑到莫比乌斯反演了

数论分块与整除相关

先补一下数学小 trick

引理 1

略证:

引理 2

表示集合 的元素个数

略证:

对于 种取值

对于 ,有 ,也只有 种取值

综上,得证

数论分块

数论分块的过程大概如下:考虑含有 的求和式子( 为常数)

对于任意一个 ,我们需要找到一个最大的 ,使得 .

.

略证:

.

利用上述结论,我们每次以 为一块,分块求和即可

狄利克雷卷积

狄利克雷卷积是建立在群 上的运算,其中 是数论函数集合,定义如下

运算律与性质

交换律: .

结合律: .

分配律: .

积性函数的卷积仍为积性函数

单位元

狄利克雷卷积的单位元为函数 ,即 时表达式为 1,否则为 0.

常用卷积

莫比乌斯函数

提到莫比乌斯反演就不得不提到的函数

定义

莫比乌斯函数 是一个数论函数,其定义如下

其中 .

性质

是一个积性函数

在狄利克雷卷积的意义下, ,即 互为逆元

使用莫比乌斯反演解题,主要使用的就是这两个性质

莫比乌斯反演

蛤?反演?

其实就是狄利克雷卷积运算不停推式子啦

许多 dalao 的博客都会给一个莫比乌斯反演的公式:

但就笔者而言,这个公式是多余的。这其实就是狄利克雷卷积运算的展开,我们可以如下描述:

所以这就是两边同时卷一个 的逆元 的结果啊

那么莫比乌斯反演一般怎么用啊

其实用的最多的是性质二的演化

【例 1】GCD 定值统计

[HAOI2011]Problem b

多组数据,求

中括号表达式意思是:当里面的布尔表达式为真时,整个表达式的值为 1,否则整个表达式为 0.

利用前缀和的思想,把下界统一为 1,再做一次矩阵上的差即可

那么答案即为

开始变形

显然我们只需枚举 的倍数,那么同时除以

考虑到 的定义

根据 反演

变换枚举顺序,我们先枚举 ,再枚举

也就是说,我们将关于 的求和符号提前,并把原来的位置的求和符号变成布尔条件,以达到等效的求和效果

这算是一个比较通用的技巧

那么,既然 ,就只需要枚举 的倍数即可,那么同除

发现中括号表达式的值始终为 1,可以忽略

再根据乘法分配律

非常友好的式子对吧

于是利用 是积性函数的性质,我们可以 求和

不过题目要求多组数据,那么我们计算 的前缀和,即可数论分块 求和。

总复杂度 .

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e5+5;
int n,a,b,c,d,k;
bool bp[N];
int p[N],cnt,u[N];
void pre_work(){// 线性筛 mu
    u[1]=bp[0]=bp[1]=1;
    for(int i=2;i<N;i++){if(!bp[i])p[++cnt]=i,u[i]=-1;
        for(int j=1;j<=cnt&&i*p[j]<N;j++){bp[i*p[j]]=1;
            if(i%p[j]==0){u[i*p[j]]=0;break;}
            else u[i*p[j]]=-u[i];
        }
    }
    for(int i=2;i<N;i++)u[i]+=u[i-1];// 前缀和处理
}
int solve(int m,int n,int g){
    m/=g,n/=g;
    int mxp=min(m,n),p=0,q,ans=0;
    while(p<mxp){++p,q=min(m/(m/p),n/(n/p));// 两个并列的分块
        ans+=(m/p)*(n/p)*(u[q]-u[p-1]);// 统计 [p,q]
        p=q;
    }
    return ans;
}
signed main(){scanf("%lld",&n);
    pre_work();
    while(n--){scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        printf("%lld\n",solve(b,d,k)-solve(a-1,d,k)-solve(b,c-1,k)+solve(a-1,c-1,k));
    }
    return 0;
}

这道题和 [POI2007]ZAP-Queries 是差不多的,有需要的可以双倍经验哦

【例 2】GCD 常数幂

有幂的形式难以演化,就变换枚举顺序

按照之前的套路处理后半部分,得到

我们可以 ,统计答案。不过有多组 询问呢?

我们知道 是可以 分块计算的,但是由于它的外面套了一个求和,还带有 的系数,无法分块做

那么我们再次变换枚举顺序,我们先枚举 再枚举

这样,我们就把向下取整的部分提到外面来了。

后半部分的求和其实就是 ,是一个积性函数

于是预处理后半部分的前缀和,做数论分块即可

【例 3】对称 LCM

先变成 的形式

开始变形

式子里有 i,j 作为系数,所以在同时除以 d 的时候,里面的要乘回来

再次变换枚举顺序,枚举 gcd

根据等差数列求和公式,令 . 同时变换枚举顺序,令 .

同样的,前半分块,后半是一个 的积性函数,预处理前缀和即可

【例 4】非对称 LCM

化成 的形式

有一个显然的结论: ,于是我们可以模仿等差数列公式的原理两两配对

处理括号里面的部分

原式即为

线性筛

考虑具体的线性筛的过程,令 . 根据卷积的性质可知 是积性函数

对于质数

.

因此在线性筛的过程中,如果互质就直接利用积性函数的性质,如果不互质就把自变量除掉它的最小质因子的幂,这样就转化成了互质的数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+6;
int pn[N],cnt;
bool vis[N];
int phi[N],f[N],t[N];//t[i] 表示 i 的最小质因子 p 的最大幂次 p^k
void sieve(int n){vis[0]=vis[1]=1,phi[0]=0,phi[1]=1,f[1]=1,t[1]=1;
    for(int i=2;i<=n;i++){if(!vis[i])pn[++cnt]=i,phi[i]=i-1,f[i]=i*phi[i]+1,t[i]=i;
        for(int j=1;j<=cnt;j++){const int pk=t[i]*pn[j],x=i*pn[j];
            if(i*pn[j]>n)break;
            vis[i*pn[j]]=1;
            if(i%pn[j]){phi[x]=phi[i]*phi[pn[j]];
                f[x]=f[i]*f[pn[j]];
                t[x]=pn[j];
            }
            else {phi[x]=phi[i]*pn[j];
                f[x]=f[i/t[i]]*(f[t[i]]+pk*phi[pk]);
                t[x]=pk;
                break;
            }
        }
    }
}
int T,n;
signed main(){scanf("%lld",&T);
    sieve(1000000);
    while(T--){scanf("%lld",&n);
        printf("%lld\n",n*(f[n]-1)/2+n);
    }
    return 0;
}

【例 5】带有系数的 GCD 统计

[LuoguP3768] 简单的数学题,求

是质数。

看似是一道和 有关的题,不过由于带有系数,并不容易化简

我们利用 反演

做数论分块, 的前缀和用杜教筛处理:

杜教筛(见 杜教筛 - 例 3)完了是这样的

分块递归求解即可,复杂度 .

【例 6】约数个数统计

[SDOI2015] 约数个数和,多组数据,求

表示约数个数

要推这道题首先要了解 函数的一个特殊性质

再化一下这个式子

将上述式子代回原式

那么 预处理 的前缀和, 分块处理询问,总复杂度 .

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e4+5;
int n,m,T,pr[N],mu[N],d[N],t[N],cnt;//t 表示 i 的最小质因子出现的次数
bool bp[N];
void prime_work(int k){bp[0]=bp[1]=1,mu[1]=1,d[1]=1;
    for(int i=2;i<=k;i++){if(!bp[i])pr[++cnt]=i,mu[i]=-1,d[i]=2,t[i]=1;
        for(int j=1;j<=cnt&&i*pr[j]<=k;j++){bp[i*pr[j]]=1;
            if(i%pr[j]==0){mu[i*pr[j]]=0,d[i*pr[j]]=d[i]/(t[i]+1)*(t[i]+2),t[i*pr[j]]=t[i]+1;break;}
            else mu[i*pr[j]]=-mu[i],d[i*pr[j]]=d[i]<<1,t[i*pr[j]]=1;
        }
    }
    for(int i=2;i<=k;i++)mu[i]+=mu[i-1],d[i]+=d[i-1];
}
int solve(){int res=0,mxi=min(n,m);
    for(int i=1,j;i<=mxi;i=j+1)
        j=min(n/(n/i),m/(m/i)),res+=d[n/i]*d[m/i]*(mu[j]-mu[i-1]);
    return res;
}
signed main(){scanf("%lld",&T);
    prime_work(50000);
    while(T--){scanf("%lld%lld",&n,&m);
        printf("%lld\n",solve());
    }
    return 0;
}

【例 7】无平方因子的数统计

我们考虑 的贡献。当且仅当 不含平方及以上的因子时, ,否则 .

因此我们要求 中无平方因子的数的个数。那么考虑容斥,用整体减掉含有平方因子的数:

是容斥系数。

小结

举了 4 个例子,接下来总结一下

  1. 莫比乌斯反演反演其实也不是什么复杂的算法,就是在和式变形的时候偶尔辅助变换一下
  2. 对于布尔一类的求和一般考虑 来变形
  3. 对于直接贡献的可以考虑变换枚举顺序使之变成系数,或者用 来变形
  4. 处在分母位置上的一定要变换枚举顺序,不要尝试在分母上变换求和,而要在全局下变换
  5. 要灵活变换枚举的条件(比如 ),灵活观察式子的形态以转化成常见的积性函数(例 4)
  6. 对于含有向下取整的式子要变换枚举顺序提到前面来,方便数论分块
  7. 利用积性函数的性质考虑线性筛,范围较大的考虑杜教筛

莫比乌斯反演扩展

结尾补一个不常用的

放一个莫比乌斯反演非卷积形式的公式

对于数论函数 完全积性函数

我们证明一下

枚举 ij 的乘积 T

参考文献

https://blog.sengxian.com/algorithms/mobius-inversion-formula , Sengxian s Blog

https://oi-wiki.org//math/mobius/ , OI-WIKI


  转载请注明: Sshwy's Blog 莫比乌斯反演小结

 上一篇
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
下一篇 
[LuoguP2764] 最小路径覆盖问题 [LuoguP2764] 最小路径覆盖问题
DAG 的最小路径点覆盖给定有向图 。设 的一个简单路(顶点不相交的路)的集合。 如果 中每个顶点恰好在 的一条路上,则称 的一个路径覆盖。 中路径可以从 $V
2019.01.05
  目录