当时数论学到莫比乌斯暂时放下了，现在重新拿起来学习一下 定义 ---
已知 \[F(n)=\sum_{d\mid n}f(d)\] 则有 \[f(n)=\sum_{d\mid n}\mu(d)F({n\over d})\] 其中\(\mu(d)\)叫做莫比乌斯函数,其值为 \[\mu(d)=\begin{cases} 1 &\text{d = 1}\\ (-1)^r &\text{$d=p_1p_2…p_r,其中p_i为不同的素数$}\\ 0 &\text{else} \end{cases}\]
性质
- \[\sum _{ d|n }^{ }{ \mu (d)= } \begin{cases} 1,\quad n=1 \\ 0,\quad n>1 \end{cases}\\\]
证明如下:
\(\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}\)个,所以 \[\sum _{ d|n }^{ }{ \mu (d) } =C_{ k }^{ 0 }-C_{ k }^{ 1 }+C_{ k }^{ 2 }-...+{ (-1) }^{ k }C_{ k }^{ k }=\sum _{ i=0 }^{ k }{ { (-1) }^{ i }C_{ k }^{ i } } ={ (-1+1) }^{ k }=0\]
- \[\sum _{ d|n }^{ }{ \frac { \mu (d) }{ d } } =\frac { \varphi (n) }{ n }\\ \] 证明如下:
由欧拉函数性质知\(n=\sum _{ d|n }^{ }{ \varphi (n) }\), 设\(F(n)=n,\quad f(n)=\varphi (n)\), 有$f(n)=(n)={ d|n }^{ }{ (d) } \(,故\){ d|n }^{ }{ } = $
3.\(\mu(n)\)为积性函数
反演定理的证明
\[\begin{align} \sum _{ d|n }^{ }{ \mu (d)\cdot F(\frac { n }{ d } ) } &=\sum _{ d|n }^{ }{ \left[ \mu (d)\sum _{ k|\frac { n }{ d } }^{ }{ f(k) } \right] } \\ &=\sum _{ d|n }^{ }{ \sum _{ d|\frac { n }{ k } }^{ }{ \left[ \mu (d)\cdot f(k) \right] } } \\ &=\sum _{ dk|n }^{ }{ \left[ \mu (d)\cdot f(k) \right] } \\ &=\sum _{ k|n }^{ }{ \left[ f(k)\sum _{ d|\frac { n }{ k } }^{ }{ \mu (d) } \right] } =f(n) \end{align}\]
其中,$_{ d| }^{ }{ (d) } $的计算用到了性质1
另一种形式
莫比乌斯公式还有一种常用的形式较为常用： \[F(d)=\sum _{ d|n }^{ }{ f(n) } \Rightarrow f(d)=\sum _{ d|n } \mu ({ \frac { n }{ d } })F(n)\]
证明同理
题目相关
嗯，今天做了几道懵逼乌斯的题目感觉的确蛮懵逼的，主要是各种公式的推导过程很是不熟悉，看来还是要多刷题加深对于反演的理解
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\)便为 \[ans=sol(b,d)-sol(a-1,d)-sol(c-1,b)+sol(a-1,c-1)\] 于是，我们只需要解决\(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)\)的个数，则有 \[F(d)=\sum _{ d|n }^{ }{ f(n) }\] 显然 \[F(x)=\left\lfloor \frac { n }{ x } \right\rfloor \cdot \left\lfloor \frac { m }{ x } \right\rfloor \] 根据反演公式 \[f(i)=\sum _{ i|d } \mu ({ \frac { d }{ i } })F(d)=\sum _{ i|d } \mu ({ \frac { d }{ i } })\cdot \left\lfloor \frac { n }{ d } \right\rfloor \cdot \left\lfloor \frac { m }{ d } \right\rfloor \] 有 \[f(1)=\sum _{ d\le n } \mu ({ d })\cdot \left\lfloor \frac { n }{ d } \right\rfloor \cdot \left\lfloor \frac { m }{ d } \right\rfloor \] 于是我们枚举一下\(d\)就能得出结果啦。
等等，枚举？范围稍稍大一点就铁定TLE啊，我们考虑 \[\left\lfloor \frac { n }{ d } \right\rfloor
\] 这个东西，显然他不是随着\(d\)的变化一定都变化的，而是只会有\(O(\sqrt { n }
)\)个取值，具体的原因在新生赛热身的这道题 的题解中有简单提到。
因此，我们对 \[\left\lfloor \frac { n }{ d }
\right\rfloor \cdot \left\lfloor \frac { m }{ d }\right\rfloor\]
这个东西相同取值的块求区间内$\(的和即可，在实际的操作过程中只需要维护一个\)$的前缀和。
代码以 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
using namespace std;
int a,b,c,d,k;
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\)的个数然后加起来……啊喂怎么可能这么简单辣…… 但是这个想法给了我们一个思路，我们先来看 \[f(p)=\sum _{ d\le n/p }^{ }{ \mu (d)\cdot \left\lfloor \frac { n/p }{ d } \right\rfloor \cdot \left\lfloor \frac { m/p }{ d } \right\rfloor = } \sum _{ d\le n/p }^{ }{ \mu (d)\cdot \left\lfloor \frac { n }{ pd } \right\rfloor \cdot \left\lfloor \frac { m }{ pd } \right\rfloor } \] 令\(T=pd\)，有 \[f(p)=\sum _{ d\le n/p }^{ }{ \mu (\frac { T }{ p } )\cdot \left\lfloor \frac { n }{ T } \right\rfloor \cdot \left\lfloor \frac { m }{ T } \right\rfloor } \] 有 \[\begin{align} \sum _{ p\le n }^{ }{ f(p) } &=\sum _{ p\le n }^{ }{ \sum _{ d\le n/p }^{ }{ \mu (\frac { T }{ p } )\cdot \left\lfloor \frac { n }{ T } \right\rfloor \cdot \left\lfloor \frac { m }{ T } \right\rfloor } } \\ &=\sum _{ T=1 }^{ n }{ \sum _{ p|T }^{ }{ \mu (\frac { T }{ p } )\cdot \left\lfloor \frac { n }{ T } \right\rfloor \cdot \left\lfloor \frac { m }{ T } \right\rfloor } } \\ &=\sum _{ T=1 }^{ n }{ \left\lfloor \frac { n }{ T } \right\rfloor \cdot \left\lfloor \frac { m }{ T } \right\rfloor \sum _{ p|T }^{ }{ \mu (\frac { T }{ p } ) } } \end{align} \] (以上\(p\)均为质数，下同） $ \(可以分块来搞，后面的这个\)_{ p|T }^{ }{ ( ) } $就不太好弄了，我们先来研究一下它
函数$g(x)=_{ p|x }^{ }{ ( ) } $
首先，我们先来说它的计算过程中用到的一个性质，之后再给出证明 \[g(kp)=\begin{cases} \mu (k),\quad p\mid k \\ \mu
(k)-g(k),\quad p\nmid k \end{cases}\] 证明：首先 \[g(kp)=\sum _{ p'|kp }^{ }{ \mu (\frac { kp
}{ p' } ) } \] （\(p'\)为质数，下同）我们把\(k\)分解 \[k={ p
}^{ a }\cdot { p }_{ 1 }^{ { a }_{ 1 } }\cdot { p }_{ 2 }^{ { a }_{ 2 }
}...{ p }_{ r }^{ { a }_{ r } }\] 1.当\(p|k\)时，有\(a\ge
1\),故 \[kp={ p }^{ a+1 }\cdot { p }_{
1 }^{ { a }_{ 1 } }\cdot { p }_{ 2 }^{ { a }_{ 2 } }...{ p }_{ r }^{ { a
}_{ r } }\] 由\(\mu\)的定义可知，只有\(p'=p\)时，$( ) \(才不等于0（否则\)p$的指数比1大），所以此时
\[\sum _{ p'|kp }^{ }{ \mu (\frac { kp
}{ p' } ) } =\mu (k)\] 2.当\(p\nmid
k\)时 \(p'=p\)时，同上文：
\[\mu (\frac { kp }{ p' } )=\mu
(k)\] \(p'\ne
p\)时，因为$\(是一个积性函数，并且\)p $，所以有 \[\mu (\frac { kp }{ p' } )=\mu (\frac { k }{
p' } )\cdot \mu(p)\] 有 \[g(kp){ |
}_{ p\ne p' }=\sum _{ p'|kp ,p'\ne p }^{ }{ \mu (\frac { kp
}{ p' } ) } =\sum _{ p'|kp,p'\ne p }^{ }{ \mu (\frac { k }{
p' } )\cdot \mu (p) } =\mu (p)\cdot \sum _{ p'|k }^{ }{ \mu
(\frac { k }{ p' } ) } \] 而 \[\mu
(p)=-1,\sum _{ p'|k }^{ }{ \mu (\frac { k }{ p' } ) }
=g(k)\] 所以 \[g(kp){ | }_{ p\ne
p' }=-g(k)\] 上面两个加起来，就得到了 \[\mu (k)-g(k),\quad p\nmid k\] 综上， \[g(kp)=\begin{cases} \mu (k),\quad p\mid k \\ \mu
(k)-g(k),\quad p\nmid k \end{cases}\]
回想一下我们线性筛的过程，发现对于\(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
using namespace std;
int a,b,c,d,k;
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.还有好多其他类型的题，到时候单独写博客吧……我也没做完……
收尾的话差不多了，总结的话有时间再写，打那么多公式简直累死了……