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

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

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

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

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

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

四道相关推荐题（课后作业）：

• [NOI2010] 能量采集

• [清华集训2012] 模积和

• [LMXOI Round 1] Dreamer

• [SDOI2017] 遗忘的集合

BiLiBiLi：@芝土密密拉

第一题

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

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

\\原式：\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 \\

第一题思路：

原式：\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。\\原式=\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

第二题思路：

原式：\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;
}