最近在准备关于莫比乌斯反演的课件,准备把例题简要整理下来,那就开始吧

1.bzoj 2190 [SDOI2008]仪仗队

求$2+\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}[gcd(x,y)==1](n\le 40000)$

最简单的做法,线性筛预处理出欧拉函数的前缀和,时间复杂度$O(n)$。

2.bzoj 2818 Gcd

求$\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{n}[gcd(x,y)==p] (n\le 10^7)$

其实就是$\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{n}{p}\rfloor}[gcd(x,y)==1]$,枚举所有质数后就是和上一道题一样做法了,双倍经验。

3.bzoj 2705 [SDOI2012]Longge的问题

求$\sum_{i=1}^{n}gcd(i,n), n\le 2^{32}$

变形一下,枚举每种gcd的值,即

$$
\begin{aligned}
&\quad\,\sum_{i=1}^{n}gcd(i,n) \\
& =\sum_{d\mid n}d \sum_{x=1}^{\frac{n}{d}}[gcd(x,\frac{n}{d})==1] \\
& =\sum_{d\mid n}d\varphi(\frac{n}{d})
\end{aligned}
$$

那么根号枚举约数,单点求欧拉函数就做完了。

时间复杂度?是个经典的东西$O(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}})=O(n^{\frac{3}{4}})$

4.bzoj 2440 [中山市选2011]完全平方数

求第$k(k\le 10^9)$个不含完全平方数因子的正整数

二分答案,转为求前$n$个数中有多少数不含完全平方因子。容斥一下,总数减去是4(2的平方)的倍数的,减去9的倍数,16的倍数不用管,前面减过了,再减去25的倍数,加上36的倍数,因为前面多减了一次…那这样就发现了容斥系数就是莫比乌斯函数。时间复杂度$O(\sqrt{n}\log{n})$

5.luogu P2257 YY的GCD(bzoj 2820)

求$\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] (n\le 10^7)$,$T(\le 10000)$组询问

bzoj 2818的加强版,把其中一个n换成了m,这样就不能用欧拉函数了,推导一下:

下述的$p$表示质数

$$
\begin{aligned}
& \quad\, \sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] \\
& =\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(x,y)==1] \\
& =\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid gcd(x,y)}\mu(d) \\
& =\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid x \land d\mid y}\mu(d) \\
& =\sum_{p}\sum_{d=1}^{\lfloor \frac{min(n,m)}{p}\rfloor}\mu(d)\lfloor \frac{n}{pd}\rfloor\lfloor \frac{m}{pd}\rfloor \\
& =\sum_{k=1}^{min(n,m)}\sum_{p,p\mid k}\mu(\frac{k}{p})\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor \\
& =\sum_{k=1}^{min(n,m)}f(k)\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor
\end{aligned}
$$

其中第三行莫比乌斯反演,第五行交换求和,第六行令$k=pd$,转而枚举$k$,化简到最后用筛法预处理出所有$f$的值即可,这里应该可以用线性筛,不过懒得推导的话也可以枚举所有质数再枚举它的倍数这样求,那么时间复杂度就和埃氏筛一样了,之后每次求一组询问就是经典的数论分块了。时间复杂度$O(n\log{\log{n}}+T\sqrt{n})$。

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000000;
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],f[N+5];
void getprime()
{
mu[1]=1;
for(int i=2;i<=N;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt && prime[j]<=N/i;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=0;i<cnt;++i)
{
int x=prime[i];
for(int j=x;j<=N;j+=x)
f[j]+=mu[j/x];
}
for(int i=1;i<=N;++i)
f[i]+=f[i-1];
}
ll calc(int n,int m)
{
if(n>m) swap(n,m);
ll ans=0;
for(int i=1,j;i<=n;i=j+1)
{
j=min(n/(n/i),m/(m/i));
ans+=1LL*(f[j]-f[i-1])*(n/i)*(m/i);
}
return ans;
}
int main()
{
getprime();
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lld\n",calc(n,m));
}
}

6.spoj LCMSUM

求$\sum_{i=1}^{n}lcm(i,n), n\le 10^{6}$,$T(\le 300000)$组询问。

$$
\begin{aligned}
&\quad\, \sum_{i=1}^{n}lcm(i,n) \\
&=\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}\\
&=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^{2}}{gcd(i,n)}+n\\
&=\frac{1}{2}\sum_{d\mid n,d\ne n}\frac{n^2}{d}\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(k,\frac{n}{d})==1]+n \\
&=\frac{1}{2}n\sum_{d\mid n,d\ne n}\frac{n}{d}\varphi(\frac{n}{d})+n \\
&=\frac{1}{2}n\sum_{d\mid n,d\ne 1}d\varphi(d)+n \\
& =\frac{1}{2}nf(n)+n
\end{aligned}
$$

这样线性筛预处理完,$O(n\log{n})$的求出函数值$f$,每次回答$O(1)$即可。

7.bzoj 2154 Crash的数字表格

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

$$
\begin{aligned}
&\quad\,\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\\
&=\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}dxy[gcd(x,y)==1] \\
&=\sum_{d=1}^{min(n,m)}d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}xy\sum_{k\mid x \land k\mid y}\mu(k) \\
&=\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\lfloor \frac{m}{d}\rfloor}\mu(k)\sum_{x=1}^{\lfloor \frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{dk}\rfloor}k^{2}xy \\
&=\sum_{T=1}^{min(n,m)}\sum_{k\mid T}kT\mu(k)g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\\
&=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\sum_{k\mid T}k\mu(k)\\
&=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)f(T)
\end{aligned}
$$

其中$g(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\frac{m(m+1)}{2}$

一开始头铁,$O(n\log{n})$求的$f(T)$的值,超时无疑,然后学习了用线性筛求积性函数$f(T)=\sum_{k\mid T}k\mu(k)$的思路。

线性筛过程分两种情况讨论

1.$prime_j$整除$i$,那么枚举$i\times prime_j$的约数$k$时,如果关于$prime_j$的指数大于等于2的话莫比乌斯函数为零,对答案没有贡献,所以此时:
$$
f(i\times prime_j)=f(i)
$$

2.$prime_j$不整除$i$,那么再分枚举的约数$k$是否含有$prime_j$,不含有的部分就是$f(i)$,含$prime_j$的话,整体乘上这么多,并且莫比乌斯函数要变号,是$-f(i)prime_j$。综上,此时:
$$
f(i\times prime_j)=(1-prime_j)f(i)
$$

这样这道题就做完了,时间复杂度$O(n)$。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=20101009;
const int N=10000000;
bool vis[N+5];
int prime[666666],cnt;
int f[N+5];
void getprime()
{
f[1]=1;
for(int i=2;i<=N;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
f[i]=(1-i+mod);
}
for(int j=0;j<cnt && i*prime[j]<=N;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])
{
f[i*prime[j]]=1LL*(1-prime[j]+mod)*f[i]%mod;
}
else
{
f[i*prime[j]]=f[i];
break;
}
}
}
// for(int i=1;i<=N;++i)
// {
// for(int j=i;j<=N;j+=i)
// {
// f[j]+=i*mu[i];
// if(f[j]<0) f[j]+=mod;
// else if(f[j]>=mod) f[j]-=mod;
// }
// }
}
int Sum(int n)
{
return 1LL*(n+1)*n/2%mod;
}
int main()
{
getprime();
int n,m;
scanf("%d%d",&n,&m);
if(n<m) swap(n,m);
ll ans=0;
for(int i=1;i<=m;++i){
ans+=1LL*i*Sum(n/i)%mod*Sum(m/i)%mod*f[i]%mod;
if(ans>=mod) ans-=mod;
}
printf("%lld\n",ans);
}

8.bzoj 3994 [SDOI2015]约数个数和

求$\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij), n,m\le 50000$,$T(\le 50000)$组询问,其中$d$是约数个数函数。

这个题一开始卡在一个结论上了,首先要知道$d(ij)=\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]$,这个结论不好想,但可以用分解质因数的形式结合约数个数定理推出来,那解决了第一步,后面的就简单了。

$$
\begin{aligned}
&\quad\,\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid gcd(x,y)}\mu(k)\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid x \land k\mid y}\mu(k)\\
&=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor\\
&=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor f(\lfloor\frac{m}{k}\rfloor)\\
&=\sum_{k=1}^{min(n,m)}\mu(k)f(\lfloor\frac{n}{k}\rfloor) f(\lfloor\frac{m}{k}\rfloor) \\
\end{aligned}
$$

至此又可以数论分块搞定单组询问了,时间复杂度$O(T\sqrt{n})$。

9.bzoj 4659 lcm

化简下题意就是求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)[\mu^2(gcd(i,j))==1],n,m\le 4000000$,对$2^{30}$取模,$T(\le 2000)$组询问。发现就是在第七题的基础上加了个多组询问,且只统计$\mu^2(gcd(i,j))==1$的。

那么前面的推导都是一样的,最后化简到

原式$=\sum_{T=1}^{min(n,m)}g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)T\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})$

头铁依然会TLE,还是先观察一下

$f(T)=\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})$是积性函数

且当$T$分解质因数后的指数中有大于2的情况的话,显然此时$f(T)=0$,并且易知$f(p)=1-p,f(p^2)=-p$,这样又可以线性筛搞一搞了,然后预处理出$if(i)$的前缀和。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1<<30;
const int N=4000000;
bool vis[N+5];
int prime[N+5],cnt;
unsigned int f[N+5],sum[N+5];
void getprime() {
f[1]=1;
for(int i=2;i<=N;i++) {
if(!vis[i]) {
prime[cnt++]=i;
f[i]=1U-i;
}
for(int j=0;j<cnt && i*prime[j]<=N;j++) {
vis[i*prime[j]]=true;
if(i%prime[j]) {
f[i*prime[j]]=f[i]*f[prime[j]];
}
else {
if(i==prime[j]) f[i*prime[j]]=-prime[j];
else if(i/prime[j]%prime[j]==0) f[i*prime[j]]=0;
else f[i*prime[j]]=f[i/prime[j]]*f[prime[j]*prime[j]];
break;
}
}
}
// for(int i=1;i<=N;++i) {
// for(int j=i;j<=N;j+=i) {
// f[j]+=i*mu[i]*abs(mu[j/i]);
// }
// }
for(int i=1;i<=N;++i)
sum[i]=sum[i-1]+1U*i*f[i];
}
unsigned int Sum(int n)
{
return 1LL*(n+1)*n/2;
}
int main()
{
getprime();
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
if(n<m) swap(n,m);
unsigned int ans=0;
for(int i=1,j;i<=m;i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=1U*(sum[j]-sum[i-1])*Sum(n/i)*Sum(m/i);
}
printf("%d\n",(int)(ans%mod));
}
}

10.bzoj 4816 [Sdoi2017]数字表格

求$\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)),n,m\le 10^6$,其中$f$为斐波那契数列,结果模$10^9+7$,$T(\le 1000)$组询问。

$$
\begin{aligned}
&\quad\,\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)) \\
&=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)==1]} \\
&=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{k=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\\
\end{aligned}
$$

这样指数部分是关于$\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor$的函数,可以分块,又因为外层是枚举的$d$,所以分块套分块即可!时间复杂度$O(T(n^{\frac{3}{4}}+\sqrt{n}\log{n}))$,前一部分来源分析同第三题

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
#define N 1000000
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],sum[N+5];
int f[N+5],pre[N+5];
void getprime() {
mu[1]=1;
for(int i=2;i<=N;i++) {
if(!vis[i]) {
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt && prime[j]<=N/i;j++) {
vis[i*prime[j]]=true;
if(i%prime[j])
mu[i*prime[j]]=-mu[i];
else {
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=1;i<=N;++i)
sum[i]=sum[i-1]+mu[i];
}
int power(int x,ll n){
int ans=1;
while(n){
if(n&1) ans=1LL*ans*x%mod;
x=1LL*x*x%mod;
n>>=1;
}
return ans;
}
ll calc(int n,int m,int d){
ll ans=0;
for(int i=1,j;i<=n;i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=1LL*(sum[j]-sum[i-1])*(n/i)*(m/i);
}
return ans;
}
int main(){
getprime();

pre[0]=pre[1]=f[1]=1;
for(int i=2;i<=N;++i){
f[i]=f[i-1]+f[i-2];
if(f[i]>=mod) f[i]-=mod;
pre[i]=1LL*pre[i-1]*f[i]%mod;
}
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
int ans=1;
for(int i=1,j;i<=n;i=j+1){
j=min(n/(n/i),m/(m/i));
int x=1LL*pre[j]*power(pre[i-1],mod-2)%mod;
ll y=calc(n/i,m/i,i);
ans=1LL*ans*power(x,y)%mod;
}
printf("%d\n",ans);
}
}