莫比乌斯反演的证明及应用(包含杜教筛)

发表于 更新于 分类于

懵 逼 钨 丝

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

前置知识

1.卷积

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

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

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

那么让我们设想一个单位元数论函数$\iota$，这个$\iota$满足$(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^{n}_{i=1}\sum^{m}_{j=1}lcm(i,j)$

显而易见是莫反题

$\sum^{n}_{i=1}\sum^{m}_{j=1}lcm(i,j)$.

可变为

$\sum^{min(n,m)}_{k=1}\sum^{n}_{i=1}\sum^{m}_{j=1}ij/k[gcd(i,j)=k]$.

然后变为

$\sum^{min(n,m)}_{k=1}\sum^{n/k}_{i=1}\sum^{m/k}_{j=1}ijk*[gcd(i,j)=1]$.

等于

$\sum^{min(n,m)}_{k=1}\sum^{n/k}_{i=1}\sum^{m/k}_{j=1}ijk*\sum_{d\mid gcd(i,j)}\mu(d)$.

上面又等于

$\sum^{min(n,m)}_{k=1}k\sum^{n/k}_{i=1}i\sum^{m/k}_{j=1}j\sum_{d\mid gcd(i,j)}\mu(d)$

然后枚举$d$

可得

$\sum^{min(n,m)}_{k=1}k\sum^{min(n/k,m/k)}_{d=1}\mu(d)d^2\sum^{n/kd}_{i=1}i\sum^{m/kd}_{j=1}j$

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

然后除法搞定。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

杜教筛

明天更新

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}