高级数论浅讲:莫比乌斯反演

luoran 2024-2-6 281 2/6

莫比乌斯反演作为数论与组合数学中的重要内容,在学习莫反前请先具备一定数论与组合数学相关知识。

推荐阅读:https://blog.xecades.xyz/articles/DirichletConvolution/

本次课通过两道例题来介绍高级数论莫比乌斯反演在信息学竞赛中的考察。

莫比乌斯反演相关题型主要在于式子推导及变换处理。

本次课选取的题目不算难,以单独的莫比乌斯反演为主。

事实上,莫比乌斯反演还可再结合积性函数、Dirichlet卷积、容斥原理、矩阵快速幂、乘法逆元、生成函数、FFT快速傅里叶变换等进行考察。

四道相关推荐题(课后作业):

  • [NOI2010] 能量采集

  • [清华集训2012] 模积和

  • [LMXOI Round 1] Dreamer

  • [SDOI2017] 遗忘的集合

BiLiBiLi:@芝土密密拉

第一题

[蓝桥杯 2018 国 B] 矩阵求和

第一题式子详细推导过程:

原式:i=1nj=1ngcd(i,j)2=i=1nj=1nk=1nk2[gcd(i,j)=k]=i=1nkj=1nkk=1nk2[gcd(i,j)=1]=k=1nk2i=1nkj=1nk[gcd(i,j)=1]=k=1nk2i=1nkj=1nkdgcd(i,j)nkμ(d)=k=1nk2i=1nkj=1nkd=1nkμ(d)[di][dj]=k=1nk2d=1nkμ(d)i=1nk[di]j=1nk[dj]=k=1nk2d=1nkμ(d)nkdnkd\\原式:\sum_{i=1}^{n} \sum_{j=1}^{n}gcd(i,j) ^2\\ =\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} k^2[gcd(i,j)=k]\\=\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{k=1}^{n} k^2[gcd(i,j)=1]\\=\sum_{k=1}^{n} k^2\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } [gcd(i,j)=1]\\=\sum_{k=1}^{n} k^2\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{n}{k}  \right \rfloor }\sum_{d|gcd(i,j)}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\\=\sum_{k=1}^{n} k^2\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{n}{k}  \right \rfloor }\sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)[d|i][d|j]\\=\sum_{k=1}^{n} k^2\sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } [d|i]\sum_{j=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } [d|j] \\=\sum_{k=1}^{n} k^2\sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\left \lfloor \frac{n}{kd}  \right \rfloor \left \lfloor \frac{n}{kd}  \right \rfloor \\

第一题思路:

原式:i=1nj=1ngcd(i,j)2最终式:k=1nk2d=1nkμ(d)nkdnkdF(n)=d=1nμ(d)ndndF(n),易分块处理。问题即转化为k=1nk2F(nk)原式:\sum_{i=1}^{n} \sum_{j=1}^{n} gcd(i,j)^2\\最终式:\sum_{k=1}^{n} k^{2}  \sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\left \lfloor \frac{n}{kd}  \right \rfloor \left \lfloor \frac{n}{kd}  \right \rfloor\\令F(n)=\sum_{d=1}^n \mu (d)\left \lfloor \frac{n}{d}  \right \rfloor \left \lfloor \frac{n}{d}  \right \rfloor\\对F(n),易分块处理。\\问题即转化为\sum_{k=1}^{n} k^{2} F(\frac{n}{k})。

第一题C++程序代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
const int N=1e7+5,mod=1e9+7;
int primes[N],pj,mu[N],n,p[N];
bool st[N];
void init(){
    int n=N-1;
    mu[1]=1;
    rep(i,2,n){
        if(!st[i]){
            primes[++pj]=i;
            mu[i]=-1;
        }
        for(int j=1;i*primes[j]<=n;j++){
            int m=i*primes[j];
            st[m]=1;
            if(i%primes[j]==0){
                mu[m]=0;
                break;
            }else mu[m]=-mu[i];
        }
    }
    rep(i,1,n){
        mu[i]+=mu[i-1];
        p[i]=(p[i-1]+1LL*i*i%mod)%mod;
    }
}
int F(int x){
    int res=0;
    for(int l=1,r;l<=x;l=r+1){
        r=x/(x/l);
        res=(res+1LL*(mu[r]-mu[l-1])*(x/l)*(x/l)%mod)%mod;
    }
    return res;
}
int calc(){
    int res=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        res=(res+(p[r]-p[l-1]+mod)%mod*1LL*F(n/l)%mod)%mod;
    }
    return res;
}
int main(){
    init();
    cin>>n;
    cout<<calc();
    return 0;
}

第二题

[国家集训队] Crash的数字表格

第二题式子详细推导过程:

n<m原式=i=1nj=1mlcm(i,j)=i=1nj=1mijgcd(i,j)=i=1nj=1mk=1nij [gcd(i,j)=k]k=i=1nkj=1mkk=1nk2ij [gcd(i,j)=1]k=k=1ni=1nkj=1mkkij [gcd(i,j)=1]=k=1nki=1nkj=1mkijdgcd(i,j)nkμ(d)=k=1nki=1nkj=1mkijd=1nkμ(d)[di][dj]=k=1nki=1nki[di]j=1mkj[dj]d=1nkμ(d)=k=1nki=1nkdidj=1mkdjdd=1nkμ(d)=k=1nkd=1nkμ(d)d2i=1nkdij=1mkdj设n<m。\\原式=\sum_{i=1}^{n} \sum_{j=1}^{m}lcm(i,j)\\=\sum_{i=1}^{n} \sum_{j=1}^{m} \frac{ij}{gcd(i,j)} \\=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{n} \frac{ij \ [gcd(i,j)=k]}{k} \\=\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{m}{k}  \right \rfloor } \sum_{k=1}^{n} k^2\frac{ij \ [gcd(i,j)=1]}{k} \\=\sum_{k=1}^{n} \sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{m}{k}  \right \rfloor }  kij \ [gcd(i,j)=1]\\=\sum_{k=1}^{n} k\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{m}{k}  \right \rfloor }  ij \sum_{d|gcd(i,j)}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\\=\sum_{k=1}^{n} k\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{m}{k}  \right \rfloor }  ij \sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)[d|i][d|j]\\=\sum_{k=1}^{n} k\sum_{i=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } i[d|i]\sum_{j=1}^{\left \lfloor \frac{m}{k}  \right \rfloor }  j[d|j] \sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\\=\sum_{k=1}^{n} k\sum_{i=1}^{\left \lfloor \frac{n}{kd}  \right \rfloor } id\sum_{j=1}^{\left \lfloor \frac{m}{kd}  \right \rfloor }  jd \sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)\\=\sum_{k=1}^{n} k \sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d) d^2\sum_{i=1}^{\left \lfloor \frac{n}{kd}  \right \rfloor } i\sum_{j=1}^{\left \lfloor \frac{m}{kd}  \right \rfloor }  j

第二题思路:

原式:i=1nj=1mlcm(i,j)最终式:k=1nkd=1nkμ(d)d2i=1nkdij=1mkdjF(n,m)=d=1nμ(d)d2i=1ndij=1mdjG(n,m)=i=1nij=1mj问题即转化为k=1nkF(n,m)F(n,m)=d=1nμ(d)d2G(n,m)原式:\sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i,j)\\最终式:\sum_{k=1}^{n} k\sum_{d=1}^{\left \lfloor \frac{n}{k}  \right \rfloor } \mu (d)d^2\sum_{i=1}^{\left \lfloor \frac{n}{kd}  \right \rfloor } i\sum_{j=1}^{\left \lfloor \frac{m}{kd}  \right \rfloor } j\\令F(n,m)=\sum_{d=1}^n \mu (d)d^2\sum_{i=1}^{\left \lfloor \frac{n}{d}  \right \rfloor } i\sum_{j=1}^{\left \lfloor \frac{m}{d}  \right \rfloor } j\\令G(n,m)=\sum_{i=1}^n i\sum_{j=1}^m j\\问题即转化为\sum_{k=1}^{n} k F(n,m),F(n,m)=\sum_{d=1}^n \mu (d)d^2G(n,m)。

第二题C++程序代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
const int N=1e7+5,mod=20101009;
int n,m,primes[N],pj,mu[N],s[N];
bool st[N];
void init(){
    int n=N-1;
    mu[1]=1;
    rep(i,2,n){
        if(!st[i]){
            primes[++pj]=i;
            mu[i]=-1;
        }
        for(int j=1;i*primes[j]<=n;j++){
            int m=i*primes[j];
            st[m]=1;
            if(i%primes[j]==0){
                mu[m]=0;
                break;
            }else mu[m]=-mu[i];
        }
    }
    rep(i,1,n) s[i]=((s[i-1]+1ll*mu[i]*i*i)%mod+mod)%mod;
}
int G(int n,int m){
    return (1ll*n*(n+1)/2%mod)*(1ll*m*(m+1)/2%mod)%mod;
}
int F(int n,int m){
    int res=0;
    for(int l=1,r;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        res=(res+1ll*(s[r]-s[l-1])%mod*G(n/l,m/l)%mod+mod)%mod;
    }
    return res;
}
int calc(){
    if(n>m) swap(n,m);
    int res=0;
    for(int l=1,r;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        res=(res+1ll*(r-l+1)*(l+r)/2%mod*F(n/l,m/l)%mod)%mod;
    }
    return res;
}
int main(){
    init();
    cin>>n>>m;
    cout<<calc();
    return 0;
}
- THE END -
最后修改:2024年2月6日
1

非特殊说明,本博所有文章均为博主原创。

共有 0 条评论