莫比乌斯反演 学习笔记

当时数论学到莫比乌斯暂时放下了,现在重新拿起来学习一下

定义

已知

则有

其中$\mu(d)$叫做莫比乌斯函数,其值为

性质

1.

证明如下:

$\bullet$ $n=1$时,显然

$\bullet$ $n\neq 1$时,将$n$分解$n={ { p }_{ 1 } }^{ { a }_{ 1 } }{ { p }_{ 2 } }^{ { a }_{ 2 } }…{ { p }_{ k } }^{ { a }_{ k } }$, $\mu$值不为0的只有质因子次数均为1的因子,其中质因子个数为$r$的因子有$C_{k}^{r}$个,所以

2.

证明如下:

由欧拉函数性质知$n=\sum _{ d|n }^{ }{ \varphi (n) }$, 设$F(n)=n,\quad f(n)=\varphi (n)$, 有$f(n)=\varphi (n)=\sum _{ d|n }^{ }{ \mu (d) } \cdot \frac { n }{ d } $,故$\sum _{ d|n }^{ }{ \frac { \mu (d) }{ d } } =\frac { \varphi (n) }{ n } $

3.$\mu(n)$为积性函数

反演定理的证明

其中,$\sum _{ d|\frac { n }{ k } }^{ }{ \mu (d) } $的计算用到了性质1

另一种形式

莫比乌斯公式还有一种常用的形式较为常用:

证明同理

题目相关

嗯,今天做了几道懵逼乌斯的题目感觉的确蛮懵逼的,主要是各种公式的推导过程很是不熟悉,看来还是要多刷题加深对于反演的理解

1.区间内$gcd(x,y)=k$对数查询

这是第一类的莫比乌斯反演的应用问题,详细的题意为”求满足$a\le x\le b, c\le y\le d$范围内,$gcd(x,y)=k$的$(x,y)$数对有多少个”。
首先,我们将问题转化成四个子问题,如果$sol(a,b)$表示$1\le x\le a, 1\le y\le b$范围内满足题意的$(x,y)$数对有多少个,那么最后的答案$ans$便为

于是,我们只需要解决$1\le x\le a, 1\le y\le b$范围内$gcd(x,y)=k$的个数。
显然,这个问题等价于$1\le x\le \frac { a }{ k } ,1\le y\le \frac { b }{ k } $范围内$gcd(x,y)=1$的个数。
于是,我们考虑这个元问题:$1\le x\le n ,1\le y\le m $范围内$gcd(x,y)=1$的个数
不妨假设$n\le m$ 我们用$f(k)$表示$gcd(x,y)=k$的个数,用$F(k)$表示$k|gcd(x,y)$的个数,则有

显然

根据反演公式

于是我们枚举一下$d$就能得出结果啦。

等等,枚举?范围稍稍大一点就铁定TLE啊,我们考虑

这个东西,显然他不是随着$d$的变化一定都变化的,而是只会有$O(\sqrt { n } )$个取值,具体的原因在新生赛热身的这道题 的题解中有简单提到。
因此,我们对

这个东西相同取值的块求区间内$\mu $的和即可,在实际的操作过程中只需要维护一个$\mu $的前缀和。 代码以 BZOJ_2301 为例

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int a,b,c,d,k;
#define N 100100
#define LL long long
int prim[N], phi[N] = {1,1}, mob[N]={1,1};
bool vis[N];
int pn = 0;
LL sum[N];
void table(){
memset(vis, 0, sizeof(vis));
mob[1]=1;
for(int i = 2;i < N;i++){
if(!vis[i]) {
prim[pn++] = i;
phi[i] = i-1;
mob[i] = -1;
}
for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){
if(i % prim[j] == 0){
phi[i*prim[j]] = phi[i] * prim[j];
vis[i*prim[j]] = 1;
mob[i*prim[j]] = 0;
break;
}
phi[i*prim[j]] = phi[i] * (prim[j]-1);
vis[i*prim[j]] = 1;
mob[i*prim[j]] = -mob[i];
}
}
sum[0]=0;
for(int i=1;i<N;i++) sum[i]=sum[i-1]+mob[i];
}

LL sol(int n,int m)
{
int last;
LL ret=0;
if(n>m) swap(n,m);
for(int i=1;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
ret+=(LL)(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return ret;
}
int main()
{
int T;
table();
for(scanf("%d",&T);T--;){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
LL ans=sol(b/k,d/k)-sol((a-1)/k,d/k)-sol((c-1)/k,b/k)+sol((a-1)/k,(c-1)/k);
printf("%lld\n",ans);
}
return 0;
}

2.区间内$gcd(x,y)$为质数的对数查询

同1.可转化成元问题:$1\le x\le n ,1\le y\le m $范围内$gcd(x,y)$为质数的$(x,y)$数对个数 $(n\le m)$ 一个非常直观(或说偷懒)的办法就是对于所有的质数$p$满足$p\le n$我们用1.的方法搞出$gcd(x,y)=p$的个数然后加起来……啊喂怎么可能这么简单辣……
但是这个想法给了我们一个思路,我们先来看

令$T=pd$,有

(以上$p$均为质数,下同)
$\left\lfloor \frac { n }{ T } \right\rfloor \cdot \left\lfloor \frac { m }{ T } \right\rfloor $可以分块来搞,后面的这个$\sum _{ p|T }^{ }{ \mu (\frac { T }{ p } ) } $就不太好弄了,我们先来研究一下它

函数$g(x)=\sum _{ p|x }^{ }{ \mu (\frac { x }{ p } ) } $

首先,我们先来说它的计算过程中用到的一个性质,之后再给出证明

证明:首先

($p’$为质数,下同)我们把$k$分解

1.当$p|k$时,有$a\ge 1$,故

由$\mu$的定义可知,只有$p’=p$时,$\mu (\frac { kp }{ p’ } ) $才不等于0(否则$p$的指数比1大),所以此时

2.当$p\nmid k$时 $p’=p$时,同上文:

$p’\ne p$时,因为$\mu $是一个积性函数,并且$p\nmid \frac { k }{ p’ } $,所以有

所以

上面两个加起来,就得到了

综上,

回想一下我们线性筛的过程,发现对于$p|k$和$p\nmid k$的讨论正是线性筛的过程,因此我们可以预处理出$g(x)$,然后的做法就和问题1差不多了,具体的预处理过程看代码还是。 貌似一道叫做 YY的GCD 的题目成了权限题,于是代码只好以 SPOJ_PGCD 为例

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int a,b,c,d,k;
#define N 10000005
#define LL long long
int prim[N], phi[N] = {1,1}, mob[N]={1,1},g[N];
bool vis[N];
int pn = 0;
LL sum[N];
void table(){
memset(vis, 0, sizeof(vis));
mob[1]=1;
g[1]=1;
for(int i = 2;i < N;i++){
if(!vis[i]) {
prim[pn++] = i;
phi[i] = i-1;
mob[i] = -1;
g[i] = 1;
}
for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){
if(i % prim[j] == 0){
phi[i*prim[j]] = phi[i] * prim[j];
vis[i*prim[j]] = 1;
mob[i*prim[j]] = 0;
g[i*prim[j]] = mob[i];
break;
}
phi[i*prim[j]] = phi[i] * (prim[j]-1);
vis[i*prim[j]] = 1;
mob[i*prim[j]] = -mob[i];
g[i*prim[j]] = mob[i] - g[i];
}
}
sum[0]=0;
for(int i=1;i<N;i++) sum[i]=sum[i-1]+g[i];
}

LL sol(int n,int m)
{
int last;
LL ret=0;
if(n>m) swap(n,m);
for(int i=1;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
ret+=(LL)(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return ret-(LL)m*n;
}
int main()
{
int T,cas=1;
table();
for(scanf("%d",&T);T--;){
scanf("%d%d",&a,&b);
LL ans;
ans=sol(a,b);
printf("%lld\n",ans);
}
return 0;
}

3.还有好多其他类型的题,到时候单独写博客吧……我也没做完……

收尾的话差不多了,总结的话有时间再写,打那么多公式简直累死了……