本文参考借鉴于知乎上$Syu Gau$与$阮行止$在$如何证明莫比乌斯反演？$这一问题下的回答.

前置知识

1.卷积

首先我们先设$f,g$为两个数论函数。

则卷积定义为$(f\times g)(n)=\sum_{ij=n}f(i)g(j)$。(注意本文的$\times$不是乘,是卷积运算，乘都已省略)

易证卷积满足交换律与结合律。

那么让我们设想一个单位元数论函数$a$，这个$a$满足$(a\times f)(n)=f(n)$

那就要满足$(f\times a)(n)=\sum_{ij=n}f(i)a(j)$

显然$a(n)=[n=1]$

让我们继续定义，通过狄利克雷卷积可知

对于$f,g$数论函数，还有一种卷积写法为$(f\times g)(n)=\sum_{d\mid n}f(d)g(n/d)$

用你的膝盖想一想，你会发现$(f\times g)(n)=\sum_{d\mid n}f(d)g(n/d)=\sum_{ij=n}f(i)g(j)$这两种写法完全等价。

OK，到此前置知识全部讲完，让我们开始证明莫比乌斯反演。

我们要证明当有$F(n)=\sum_{d\mid n}g(d)=\sum_{d\mid n}g(n/d)$时,$g(n)=\sum_{d\mid n}\mu(d)F(n/d)=\sum_{d\mid n}\mu(n/d)F(d)$

考虑转化为狄利克雷卷积,我们设一个函数$b$,它把所有数都映射成1.

则原问题被转化为已知$F=g\times b$。

求证$g=F\times \mu$

因为单位元函数的性质，任何函数卷上它都是自己本身，所以有$F\times a=g\times b$

因为莫比乌斯函数定义则$\mu\times b=a$

这个很好证$(\mu\times b)(n)=\sum_{d\mid n}\mu(d)$

而$\mu$函数有个性质就是$\sum_{d\mid n}\mu(d)=[n=1]$

所以上式成立（极不严谨）。

那么$F\times a=g\times b$

可化为$b\times F\times \mu=g\times b$

两边把$b$逆元一卷，完美消掉。

便证得$g=F\times \mu$

也就有$g(n)=\sum_{d\mid n}\mu(d)f(n/d)=\sum_{d/n}\mu(n/d)f(d)$

应用

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

就是求$ \sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j)$

显而易见是莫反题

$ \sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j)$

可变为

${\textstyle\sum_{k=1}^{min(n,m)}}{\textstyle\sum_{i=1}^n}{\textstyle\sum_{j=1}^m}\frac{i\ast j}k\lbrack gcd(i,j)=k\rbrack$

然后变为

${\textstyle\sum_{k=1}^{min(n,m)}}{\textstyle\sum_{i=1}^{\displaystyle\frac nk}}{\textstyle\sum_{j=1}^{\displaystyle\frac mk}}i\ast j\ast k\sum_{d\vert gcd(i,j)}\mu(d)$

上面又等于

${\textstyle\sum_{k=1}^{min(n,m)}}{\textstyle k\sum_{i=1}^{\displaystyle\frac nk}}{\textstyle i\sum_{j=1}^{\displaystyle\frac mk}}\underset{d\vert gcd(i,j)}{j\sum}\mu(d)$

然后枚举$d$

可得

${\textstyle\sum_{k=1}^{min(n,m)}}{\textstyle k\sum_{d=1}^{min({\displaystyle\frac nk},{\displaystyle\frac mk})}d^2\ast\mu(d)\sum_{i=1}^{\displaystyle\frac n{kd}}}{\textstyle i\sum_{j=1}^{\displaystyle\frac m{kd}}}j$

显而易见这个$\mu(d)d^2$是积性函数可以筛，这个自己推导下。

然后除法搞定。

代码

#include<bits/stdc++.h>
#define Maxn 10000005
#define Mod 20101009
#define LL long long
using namespace std;
LL prime[2*Maxn],g[2*Maxn],sum[2*Maxn],N,M,cnt=0,Ans=0,p[2*Maxn];
bool is_prime[2*Maxn];
int main()
{
    scanf("%lld%lld",&N,&M);
    memset(is_prime,1,sizeof(is_prime));
    is_prime[0]=is_prime[1]=0;g[1]=1;
    for (int i=1;i<=Maxn-5;i++)
    {
        if (is_prime[i]) g[i]=(1-i+Mod)%Mod,prime[++cnt]=i;
        for (int j=1;j<=cnt&&i*prime[j]<=Maxn-5;j++)
        {
            is_prime[i*prime[j]]=0;
            g[i*prime[j]]=g[i]*g[prime[j]]%Mod;
            if (i%prime[j]==0) {g[i*prime[j]]=g[i];break;}
        }
    }

    for (int i=1;i<=Maxn-5;i++) sum[i]=(sum[i-1]+(g[i]*i%Mod))%Mod;
    for (int i=1;i<=Maxn-5;i++) p[i]=(p[i-1]+i)%Mod;
    if (N>M) swap(N,M);
    for (int l=1,r;l<=N;l=r+1)
    {
        r=min(N/(N/l),M/(M/l));
        Ans=(Ans+(((sum[r]-sum[l-1]+Mod)%Mod)*p[N/l]%Mod)*p[M/l]%Mod)%Mod;
    }
    cout<<Ans<<endl;
    return 0;
}

杜教筛

作用是筛出一个积性函数的前缀和，具体做法就是要找到另一个函数，一般为$I $或$id$，然后是公式推导

${\textstyle\sum_{i=1}^n}(f\times g)(i)={\textstyle\sum_{i=1}^n}\sum_{d \mid n}f(d)g(\frac nd)={\textstyle\sum_{d=1}^n}g(d){\textstyle\sum_{i=1}^{\displaystyle\frac nd}}f(i)={\textstyle\sum_{d=1}^n}{\textstyle g}{\textstyle(}{\textstyle d}{\textstyle)}{\textstyle S}{\textstyle u}{\textstyle m}{\textstyle(}\frac nd{\textstyle)}{\textstyle=}{\textstyle g}{\textstyle(}{\textstyle1}{\textstyle)}{\textstyle S}{\textstyle u}{\textstyle m}{\textstyle(}{\textstyle n}{\textstyle)}{\textstyle+}{\textstyle\sum_{i=2}^n}{\textstyle g}{\textstyle(}{\textstyle i}{\textstyle)}{\textstyle S}{\textstyle u}{\textstyle m}{\textstyle(}\frac ni{\textstyle)}$

$g(1)Sum(n)={\textstyle\sum_{i=1}^n}(f\times g)(i)-{\textstyle\sum_{d=2}^n}g(d)Sum(\frac nd)$

$Sum(n)=\frac{\sum_{i=1}^n(f\times g)(i)-\sum_{d=2}^ng(d)Sum(\frac nd)}{g(1)}$

分子前面的卷积用公式(一般为等差数列求和$(n+1)*n/2$或者是等差数列平方和$n(n+1)(2n+1)/6$算，后面除法分块搞定。

下面给出代码和一般常用卷积

$μ∗I=ϵ$

$φ∗I=id$

$μ∗id=φ$

代码

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
#define Maxn 3000000
using namespace std;
LL T,N;
LL cnt=0,prime[Maxn+5],mu[Maxn+5],phi[Maxn+5];
bool is_prime[Maxn+5];
LL Sum_Mu[Maxn+5],Sum_Phi[Maxn+5];
tr1::unordered_map<LL,LL> SUM_MU,SUM_PHI;
inline void Read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
LL Get_Mu_Sum(LL X)
{
    if (X<=Maxn) return Sum_Mu[X];
    if (SUM_MU[X]) return SUM_MU[X];
    LL res=1;
    for (LL l=2,r;l<=X;l=r+1)
    {
        r=X/(X/l);
        res-=(r-l+1)*Get_Mu_Sum(X/l);
    }
    return SUM_MU[X]=res;
}
LL Get_Phi_Sum(LL X)
{
    if (X<=Maxn) return Sum_Phi[X];
    if (SUM_PHI[X]) return SUM_PHI[X];
    LL res=(X+1)*X/2;
    for (LL l=2,r;l<=X;l=r+1)
    {
        r=X/(X/l);
        res-=(r-l+1)*Get_Phi_Sum(X/l);
    }
    return SUM_PHI[X]=res;
}
void Get(LL X)
{
    memset(is_prime,1,sizeof(is_prime));
    is_prime[0]=is_prime[1]=0;mu[1]=1;phi[1]=1;
    for (LL i=1;i<=Maxn;i++)
    {
        if (is_prime[i]) prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
        for (LL j=1;j<=cnt&&i*prime[j]<=Maxn;j++)
        {
            is_prime[i*prime[j]]=0;
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
            if (i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
    for (LL i=1;i<=Maxn;i++) Sum_Mu[i]=Sum_Mu[i-1]+mu[i],Sum_Phi[i]=Sum_Phi[i-1]+phi[i];
}
int main()
{
    Read(T);
    Get(N);
    while (T--)
    {
        Read(N);
        cout<<Get_Phi_Sum(N)<<" "<<Get_Mu_Sum(N)<<endl;
    }
    return 0;
}