首页 > itarticle > mobius反演学习笔记

mobius反演学习笔记

admin 1月 07, 2021 0

莫比乌斯反演是数论中的重要内容，在许多情况下能够简化运算。

参考资料

前言

以前曾经简单的看过Mobius反演的一些介绍，但是看的很不认真，趁着去ZR讲Mobius反演之前赶紧恶补一下qwq

前置知识和技巧

数论函数

数论函数即定义域为$N^+$的函数

积性函数

若对于任意一对正整数$a,b$,有$gcd(a,b) = 1$,且$f(ab) = f(a) times f(b)$,那么函数$f$称为不完全积性函数。

完全积性函数的的要求就是把$gcd(a,b) = 1$这个条件去掉

狄利克雷卷积

我们称$(f * g)(n)$是 数论函数 $f,g$的狄利克雷卷积，那么有：

$$(f * g)(n) = sum_{d|n} f(d) g(frac nd)$$

性质

狄利克雷卷积运算满足交换律、结合律和分配律。

交换律： $f * g = g * f$

结合律: $f * (g * h) = (f * g) * h$

分配律：$(f + g) * h = f * h + g * h$

单位元

定义数论函数$varepsilon(n)=[n=1]$ 为狄利克雷卷积的单位元。

$$(f * varepsilon)(n) = (varepsilon * f)(n) = sum_{d|n} varepsilon(d) f(frac nd) = f(n)$$

从上式可以看出：在狄利克雷卷积的意义下，单位元$varepsilon$函数就相当于在实数意义下的$1$。

引入

我们考虑求和函数：
$$F(n) = sum_{d | n} f(d)$$

手动计算一下$n$比较小时的情况，我们可以得到$f$和$F$之间的关系：

当$n = p^2(p in rm{prime})$时，
$$F(p) = f(1) + f(p)$$
$$F(n) = f(1) + f(p) + f(n) = f(1) + f(p) + f(p^2)$$

那么显然,
$$f(n) = F(n) - F(p) = F(p^2) - F(p)$$

因为$mu(p^2) = 0$,于是我们可以大胆的做出猜测：

$$(mu * F)(n) = f(n)$$

Mobius函数

等等，那个$mu$函数是什么意思？

$mu$函数就是俗称的$rm Mobius$函数，它的定义式是这个样子的：

$$sum_{d|n} mu(d) = [n = 1]$$

其实就是：

$$mu * 1 = varepsilon$$

但为了方便，我们经常以这种方式定义$rm Mobius$函数：

求出$n$的缩系：$n = p_1^{a_1}p_2^{a_2}…p_{varphi(n)}^{a_{varphi(n)}}$

ZhUGDJ.png

最后重要的一条，$rm Mobius$函数是不完全积性函数。

Mobius反演

Mobius反演实际上就是按照$rm Mobius$函数的性质，玄学的推出来式子啦qwq

假设有数论函数$f,g$满足：

$$f(n) = sum_{d|n} g(d)$$

在狄利克雷卷积的意义下，实际上就是

$$f = g * 1$$

那么我们把等式两边同时卷一个$mu$函数，得到

$$f * mu = g * 1 * mu$$

也就是：

$$g = f * mu$$

把狄利克雷卷积替换成式子，展开来：

$$g(n) = sum_{d|n} mu(d) f(frac nd)$$

例题

Sample Probelm #1

我们以一道例题为例，来看看Mobius反演应该如何应用.

题意就是让你求：

$$prod_{i=1}^n prod_{j=1}^n frac {lcm(i,j)}{gcd(i,j)}$$

根据小学奥数内容: $gcd(i,j) times lcm(i,j) = i times j$

$$prod_{i=1}^n prod_{j=1}^n frac {ij}{gcd(i,j)^2}$$

把$prod$符号移到分数线里面：

$$frac {prod_{i=1}^n prod_{j=1}^n ij}{prod_{i=1}^n prod_{j=1}^n gcd(i,j)^2}$$

把分子上的式子拆开就能得到：

$$prod_{i=1}^n prod_{j=1}^n ij = prod_{i=1}^n (i^n times n!) = (n!)^{2n}$$

这个东西非常好求，然后我们来考虑分母。

先不考虑那个$2$次方，我们看到的是这个式子：

$$prod_{i=1}^n prod_{j=1}^n gcd(i,j)$$

我们枚举$gcd(i,j)$的可能性:

$$prod_{d=1}^n prod_{i=1}^n prod_{j=1}^n [gcd(i,j) = d]$$

也就是：

$$prod_{d=1}^n d ^ {sum_{i=1}^n sum_{j=1}^n [gcd(i,j) == d]}$$

然后我们同时除一下$d$

$$prod_{d=1}^n d ^ {sum_{i=1}^{frac nd} sum_{j=1}^{frac nd} [gcd(i,j) == 1]}$$

只看指数：

$$sum_{i=1}^{frac nd} sum_{j=1}^{frac nd} [gcd(i,j) == 1]$$

这不就是LuoguP3455 ZAP吗！

现在我们才开始真正的Mobius反演！

由Mobius函数的定义式：

$$mu * 1 = varepsilon$$

我们把$gcd(i,j)$代入可得。

$$sum_{d|gcd(i,j)} mu(d) = [gcd(i,j) = 1]$$

所以，原式可以简化为：

$$sum_{i=1}^{frac nd} sum_{j=1}^{frac nd} sum_{k|gcd(i,j)} mu(k)$$

我们变换枚举顺序，首先枚举$d$

$$sum_{d=1}^n sum_{i=1}^{frac nd} sum_{j=1}^{frac nd} [k|gcd(i,j)] cdot mu(k)$$

同时除一下$k$:

$$sum_{d=1}^n mu(k) sum_{i=1}^{frac nd} sum_{j=1}^{frac nd} [gcd(i,j) in Z]$$

显然$gcd(i,j) in Z$恒成立，于是我们把它去掉。

$$sum_{k=1}^{min(frac nd,frac md)} sum_{i=1}^{frac {n}{kd}} sum_{j=1}^{frac {n}{kd}} mu(k)$$

然后根据乘法分配律，得到：

$$z = sum_{k=1}^{frac nd} mu(k) lfloor frac {n^2}{kd}rfloor$$

这个东西显然可以数论分块，然后我们把它带回原式计算即可。

代码就不贴了qwq

Sample Problem #2

又是一道经典题目,请读者自己按照前面的套路思考一下再看下面的题解。

我们发现，题目其实就是让求这个式子：

$$sum_{i=1}^n sum_{j=1}^m [gcd(i,j) in rm{prime}]$$

我们枚举$gcd(i,j)$的答案，质数$k$

$$sum_{k=1}^{min(n,m)} sum_{i=1}^n sum_{j=1}^m [gcd(i,j) = k] (k in rm{prime})$$

然后我们同时除一下k，得到：

$$sum_{k=1}^{min(n,m)} sum_{i=1}^{frac nk} sum_{j=1}^{frac mk} [gcd(i,j) = 1] (k in rm{prime})$$

开始喜闻乐见的Mobius反演：

$$sum_{k=1}^{min(n,m)} sum_{i=1}^{frac nk} sum_{j=1}^{frac mk} sum_{d|gcd(i,j)} mu(d)$$

变换枚举顺序：

$$sum_{d=1}^{min(n,m)} sum_{k=1}^{min(n,m)} sum_{i=1}^{frac nk} sum_{j=1}^{frac mk} [d|gcd(i,j)] cdot mu(d)$$

然后我们同时除一下$d$:

$$sum_{d=1}^{min(n,m)} sum_{k=1}^{min(n,m)} sum_{i=1}^{frac {n}{kd}} sum_{j=1}^{frac {m}{kd}} [gcd(i,j) in Z] cdot mu(d)$$

显然，原式可以简化为：

$$sum_{d=1}^{lfloor frac nk rfloor} sum_{k=1}^{n} lfloor frac {n}{kd}rfloor lfloor frac {m}{kd}rfloor mu(d)$$

然后我们设$T = kd$,代入得：

$$sum_{d=1}^{lfloor frac nk rfloor} sum_{k=1}^{n} lfloor frac {n}{T}rfloor lfloor frac {m}{T}rfloor mu(d)$$

然后我们枚举一下$T$,并把它挪到前面去：

$$sum_{T=1}^n lfloor frac {n}{T}rfloor lfloor frac {m}{T}rfloor sum_{k|T,k in prime} mu left( frac Tk right)$$

然后我们预处理一下后面的东西，最后数论分块一下，就解决问题了qwq

本题代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 


#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char (){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)   flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)    putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)    putch(q[top]);
    }
    inline void space(bool x){
      if(!x) putch('n');
      else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e7 + 2;
int T,n,m,prime[MAXN],cnt,sum[MAXN],dp[MAXN];
bool isprime[MAXN];
long long u[MAXN];
/* functions */
inline void init(){
    u[1] = 1;
    FOR(i,2,MAXN,1){
        if(!isprime[i]) u[i] = -1, prime[++cnt] = i;
        for(int j=1;j <= cnt && i * prime[j] <= MAXN; j++){
            isprime[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
            u[i * prime[j]] = -u[i];
        }
    }
    FOR(i,1,cnt,1){
        for(int j=1;j * prime[i] <= MAXN;j++) dp[j * prime[i]] += u[j];
    }
    FOR(i,1,MAXN,1) sum[i] = sum[i-1] + dp[i];
}
inline long long solve(int n,int m){
    long long ans = 0;
    if(n > m) std::swap(n,m);
    for(int i = 1,j = 0; i <= n;i = j + 1){
        j = std::min(n/(n/i),m/(m/i));
        ans += (long long)(sum[j] - sum[i-1]) * (long long)(n / i) * (long long)(m / i);
    }
    return ans;
}
int main(int argc,char *Argv[]){
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(n > m) std::swap(n,m);
        printf("%lldn",solve(n,m));
    }
    return 0;
}

总结

  • Mobius反演并不是多么难的算法，它更像是一种技巧，可以帮助你更方便的计算出式子
  • 对于布尔一类的求和一般考虑用$mu * 1 = varepsilon$来解决
  • 对于直接贡献的可以考虑变换枚举顺序使它变成系数。
  • 要学会灵活的变换枚举的顺序和内容
  • 利用积性函数的性质来用线性筛预处理，范围较大可以考虑杜教筛
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能