莫比乌斯反演

· · 个人记录

莫比乌斯反演

符号普及

规定下符号先吧

前缀

了解前缀对后面的理解很重要，不然后面全是懵的。一定要熟悉了解。

简单的小推论

\left\lfloor\frac{a}{b\times c}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor

数论分块

这个不学清楚，后面绝对完了。 求解

\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor

对于朴素的算法我们直接暴力枚举，时间复杂度O(n)

在 n 很大时并不适用，但在过程中我们发现有很多数是相同的，能不能合并求解呢？

答案是可以。

也就是说我们需要找到最大的 j 满足 \left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor

结论还挺简单的，直接记下来就好了 j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor

每次我们对区间 [i,j] 求解即可。时间复杂度为

O(\sqrt n) 
for(int head=1,rear=0;head<=n;head=rear+1){
    rear=n/(n/head);ans+=(rear-head+1)*(n/head);

积性函数

好啦现在我们开始了解下积性函数吧 （本章均默认全为积性函数）

如果两个数互素，满足

还记得之前的欧拉函数吗，之前好像说过它具有积性。 还是来正式介绍一下常见的积性函数吧 1. 单位原 $\epsilon(n)=[n=1]
  1. 常函数 1(n)=1
  2. 恒等函数 id(n)=n
  3. 欧拉函数 \phi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1] （ n 以内与 n互质的数）
  4. 莫比乌斯函数 \mu(n) （等下介绍）

务必牢记定义

Dirichlet 卷积

是时候介绍一下迪利克雷卷积了

规定

(f * g) (n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})

仔细体会这个式子，并记住。

常见卷积式

这蛮重要的！！！

介绍题目中最常用的卷积式

\mu * 1=\epsilon \phi * \ 1=Id \mu * Id = \phi

简单的结论直接记下就好

用多了就懂了

莫比乌斯函数

好！现在介绍一下陌生的莫比乌斯函数。 我们规定 1(n) 的逆为莫比乌斯函数。 也就是说 1 * \mu =\epsilon 。

那么 \mu(n) 到底是什么呢？ 给出明确的式子：

\mu(x)=\begin{cases}1&x=1 \\ (-1)^k &k\text{为本质不同的质因子的个数}\\0 & otherwises\end{cases}

由于莫比乌斯是积性函数，所以根据定义（积性）展示我们的线性筛（连上欧拉函数一起附上好了）：

void init(){
    mu[1]=1;
    phi[1]=1;
    int cnt=0;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prime[cnt++]=i;
            mu[i]=-1;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]){
                mu[i*prime[j]]=-mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
            else {
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}

性质：

由

\mu * 1 = \epsilon

得

\sum\limits_{d|n}\mu(d)=[n=1]

莫比乌斯反演

本章的重头戏

积性函数有如下性质：

如果

f(n)=\sum\limits_{d|n}g(d)

则

g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})

用数论变化的证明就免了吧。

我还是比较喜欢卷积证法

f(n)=\sum\limits_{d|n}g(d)\Rightarrow f=1 * g \Rightarrow f * \mu=1 * \mu * g \Rightarrow g = f * \mu

证毕。

做题时的简单公式推导

就推一些吧，其他的自行做题积累。

  1. \sum\limits_{i=1}^n\sum\limits_{m=1}^mf(i)g(j)\Rightarrow\sum\limits_{i=1}^n f(i) \sum\limits_{j=1}^m g(j)
  2. [ \gcd(i,j)=1 ]\Rightarrow \epsilon(\gcd(i,j))\Rightarrow \sum\limits_{d|\gcd{(i,j)}}\! \! \mu(d)
  3. \sum\limits_{i=1}^n\sum\limits_{j=1}^m[d\mid i,d\mid j]\Rightarrow \sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}1\Rightarrow\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor
  4. [k\mid\gcd(i,j)]\Rightarrow [k\mid i,k\mid j]

    应用

    其实莫比乌斯函数的运算在复杂中，又含有众多的套路。

借几道题我们来学习一下

P2257 YY的GCD

还记得之前用欧拉函数解决的这道题吗P2568 GCD

这题是升级版

但再用欧拉函数并不是很好解决

所以我们来用莫比乌斯反演来简化下计算，感受如此高妙的过程

为了慢慢理解，写的比较啰嗦，

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

套路的进行运算 2, 3式子

\sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[\gcd(i,j)=1] \sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{d|\gcd{(i,j)}}\! \! \mu(d)

把 \mu 提出来

\sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{d}\mu(d)[d\mid i,d\mid j]

利用 1 式

\sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[d\mid i,d\mid j]

利用 4 式

\sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{pd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{pd}\right\rfloor}1 \sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor

设 T=pd

\sum\limits_{T=1}\sum\limits_{p\mid T}\mu(\frac{T}{p})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor

写好看一点

\sum\limits_{T=1}^{\min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\bigg(\sum\limits_{p\mid T}\mu(\frac{T}{p})\bigg)

使用线性筛预处理所有 \sum\limits_{p\mid T}\mu(\frac{T}{p})

配合上整除分块算 \left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor 就解决了此题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
bool vis[maxn];
int mu[maxn],sum[maxn],prime[maxn];
void init(){
    int cnt=0;
    mu[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!vis[i]){
            mu[i]=-1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=maxn;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j])mu[prime[j]*i]=-mu[i];
            else {
                mu[prime[j]*i]=0;
                break;
            }
        }
    }
    for(int i=1;i<=cnt;i++)
        for(int j=1;j*prime[i]<=maxn;j++)
            sum[j*prime[i]]+=mu[j];
    for(int i=1;i<=maxn;i++)sum[i]+=sum[i-1]; 
}
int main(){
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        long long ans=0;
        for(int head=1,rear=0;head<=min(n,m);head=rear+1){
            rear=min(n/(n/head),m/(m/head));
            ans+=(long long)(n/head)*(m/head)*(sum[rear]-sum[head-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题表

可以多看看题解感受一下

  1. P3455 [POI2007]ZAP-Queries
  2. 2522 [HAOI2011]Problem b

更多试题在杜教筛讲解中给出

如果觉得好，欢迎继续学习积性函数筛法----杜教筛