Fork me on GitHub

BZOJ 2818 Gcd(莫比乌斯反演)

题目

Description

给定整数 $N$ ,求 $1 \leq x,y \leq N$ 且 $Gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对.

Input

一个整数 $N$

Output

如题

Sample Input

1
4

Sample Output

1
4

HINT

对于样例 $(2,2),(2,4),(3,3),(4,2)$ $\;$ $1 \leq N \leq 10^7$


分析

我们设 $f(n)$ 为 $gcd(x,y)=n$ 的对, $F(n)$ 为 $gcd(x,y)$ 为 $n$ 的倍数的对数,然后利用莫比乌斯反演定理,将mu函数带进来。

首先枚举每一个质数,答案就是
$$ans=\sum_{p}^{min(n,m)} \sum_{d=1}^{min(n,m)} \mu(d) \left\lfloor\frac{n}{pd}\right\rfloor \left\lfloor\frac{m}{pd}\right\rfloor$$

当然不能直接这样做,需要优化,否则就会TLE。

令 $pd=T$ ,那么有
$$ans=\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor \left\lfloor\frac{m}{T}\right\rfloor \sum_{p|T} \mu(\frac{T}{p})$$

如果能求出 $\sum_{p|T}\mu(\frac{T}{p})$ 的前缀和,这个问题就能在 $O(\sqrt n)$ 的时间解出。

只需要暴力枚举出每一个质数,去更新这个质数的倍数即可。

由 $\lim_{n\rightarrow \infty} \sum_{i=1}^{n}\frac{1}{i}=\ln n+r$ 这个结论易知每个质数更新时是均摊 $O(\log n)$ 的,而质数的个数恰好为 $O(n/\log n)$

故暴力枚举+维护前缀和的时间复杂度为 $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
const int MAXN=100010;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];
void CalPhi(int n)
{
clr(vis,0);
phi[1]=1;
tot=0;
for(int i=2;i<n;i++)
{
if(!vis[i])
{
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;j++)
{
if(i*prime[j]>n) break;
vis[i*prime[j]] == 1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i] * prime[j];
break;
}
else phi[i*prime[j]]=phi[i] * (prime[j]-1);
}
}
}

得到欧拉函数phi[],素数表prime[],素数个数tot传入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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=10000010;
int a[MAXN]={1,1},b[MAXN/10],mu[MAXN],cnt;
void init()
{
ll i,j;
mu[1]=1;
for(int i=2;i<MAXN;i++)
{
if(a[i]==0)
{
b[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&b[j]*i<MAXN;j++)
{
a[b[j]*i]=1;
if(i%b[j]==0)
{
mu[b[j]*i]=0;
break;
}
else
{
mu[b[j]*i]=-mu[i];
}
}
}
}
int main()
{
init();
int n;
ll ans=0;
scanf("%d",&n);
for(int i=1;i<=cnt&&b[i]<=n;i++)
{
ll sum=0;
for(int j=b[i];j<=n;j+=b[i])
sum+=(ll)mu[j/b[i]]*(n/j)*(n/j);
ans+=sum;
}
printf("%lld\n",ans);
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<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=1e7 + 5;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];
//refer to CSL
void CalPhi(int n)
{
clr(vis,0);
phi[1]=1;
tot=0;
for(int i=2;i<n;i++)
{
if(!vis[i])
{
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;j++)
{
if(i*prime[j]>n) break;
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
ll a[MAXN];
int main()
{
int n;
ll ans=0;
scanf("%d",&n);
CalPhi(n);
a[1]=1;
for(int i=2;i<=n;i++)
a[i]=a[i-1]+2*phi[i];
for(int i=0;i<tot;i++)
if(n/prime[i])
ans+=a[n/prime[i]];
printf("%lld\n",ans);
return 0;
}

-------------本文结束感谢您的阅读-------------
obsidian wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持是我最大的动力!