莫比乌斯反演小记

发布时间 2023-09-27 19:51:18作者: Code_AC

基本内容

莫比乌斯函数

\(\mu\) 定义为 \(1\) 的逆。

一些小性质:

  1. \(\mu * 1=\epsilon\)
  2. \(\mu * \text{id}=\varphi\)

反演内容

我的理解是:

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

典型例题

例1 P2398 GCD SUM

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

来推下式子:

先枚举 \(\gcd\)

\[\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=d] \]

再将 \(d\) 除掉:

\[\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d}\rfloor}[\gcd(i,j)=1] \]

然后莫比乌斯反演:

\[\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{k|\gcd(i,j)}\mu(k) \]

枚举 \(k\)

\[\sum\limits_{k=1}^n\mu(k)\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d}\rfloor}[k|\gcd(i,j)] \]

\(k\) 除掉:

\[\sum\limits_{k=1}^n\mu(k)\sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac{n}{dk}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{dk}\rfloor}*1 \]

\(T=dk\),整理一下:

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

由于 \(\mu*\text{id}=\varphi\)

\[\sum\limits_{T=1}^n\lfloor \frac{n}{T}\rfloor^2\varphi(T) \]

欧拉函数可以直接线性筛预处理前缀和。中间的可以用整除分块 \(\Theta(\sqrt n)\)解决。

时间复杂度瓶颈在线性筛的 \(\Theta(n)\)

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5;

int n,cnt;
int prime[MAXN],vis[MAXN],phi[MAXN],sum[MAXN];

inline void init(int n)
{
    memset(vis,0,sizeof(vis));
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=vis[i]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=prime[j];
            if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else phi[i*prime[j]]=phi[i]*prime[j];
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
    return;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    init(n);
    int ans=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(sum[r]-sum[l-1])*(n/l)*(n/l);
    }
    printf("%lld\n",ans);
    return 0;
}

例2 P1829 [国家集训队] Crash的数字表格 / JZPTAB

求:

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m\text{lcm}(i,j) \]

这道题与上题差不多,因为 \(\text{lcm}(i,j)=\frac{i\times j}{\gcd(i,j)}\)

推式子:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e7+5;
const int MOD=20101009;

int n,m,cnt;
int prime[MAXN],vis[MAXN],mu[MAXN],sum[MAXN];

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

inline int S(int r,int l=1) {return ((r+l)*(r-l+1)/2)%MOD;}
inline int Sum(int x,int y) {return ((x*(x+1)/2)%MOD)*((y*(y+1)/2)%MOD)%MOD;}

inline int solve(int x,int y)
{
    int ans=0;
    for(int l=1,r;l<=min(x,y);l=r+1)
    {
        int r1=x/(x/l),r2=y/(y/l);
        r=min(r1,r2);
        ans=(ans+(sum[r]-sum[l-1]+MOD)%MOD*Sum(x/r,y/r)%MOD)%MOD;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m; init(min(n,m));
    int ans=0;
    for(int l=1,r;l<=min(n,m);l=r+1)
    {
        int r1=n/(n/l),r2=m/(m/l);
        r=min(r1,r2);
        ans=(ans+S(r,l)*solve(n/r,m/r)%MOD)%MOD;
    }
    printf("%lld\n",(ans+MOD)%MOD);
    return 0;
}