NKOJ 3957 （BZOJ 2820）YY的GCD （莫比乌斯反演+线性筛）

发表于 |
字数统计: 628字 | 阅读时长 ≈ 3min

P3957YY的GCD

问题描述

神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了，于是向你来请教……

输入格式

第一行一个整数T 表述数据组数

接下来T行，每行两个正整数，表示N, M

输出格式

T行，每行一个整数表示第i组数据的结果

样例输入

2
10 10
100 100

样例输出

30
2791

提示

T = 10000

N, M <= 10000000

显然$Ans=\sum_{p}^{min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==p]，p为质数$
$$
令f(p)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==p],F(p)=\sum_{i=1}^{n}\sum_{j=1}^{m}[p|gcd(i,j)]
$$

$$
令N=min(n,m)，那么F(p)=\sum_{p|k}^{N}f(k)=\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor
$$

$$
反演一下，f(p)=\sum_{p|k}^{N}\mu(\frac{k}{p})F(k)=\sum_{p|k}^{N}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor
$$

$$
那么Ans=\sum_{p}^{N}f(p)=\sum_{p}^{N}\sum_{p|k}^{N}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor
$$

如果是单组询问，到这里已经可以了，但本题有多组询问，因此
$$
交换一下枚举顺序，Ans=\sum_{k=1}^{N}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\sum_{p|k}\mu(\frac{k}{p})，p为质数
$$
后面的部分可以直接枚举质数再枚举倍数预处理，复杂度接近 $O(n)​$

但显然可以线性筛处理，令其为 $g[i]$ ，当 $p[j]|i$ 时， $g[i\times p[j]]=\mu(i)$，否则 $g[i\times p[j]]=mu[i]-g[i]$

然后分块处理即可，复杂度$O(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
#include<stdio.h>
#include<algorithm>
#define N 10000005
#define ll long long
using namespace std;
ll T,P[N],tot,mu[N],g[N];
bool mark[N];
void EU()
{
	ll i,j;mu[1]=1;g[1]=0;
	for(i=2;i<N;i++)
	{
		if(!mark[i])P[++tot]=i,mu[i]=-1,g[i]=1;
		for(j=1;j<=tot&&i*P[j]<N;j++)
		if(i%P[j])mu[i*P[j]]=-mu[i],g[i*P[j]]=mu[i]-g[i],mark[i*P[j]]=1;
		else {mu[i*P[j]]=0;g[i*P[j]]=mu[i];mark[i*P[j]]=1;break;}
	}
	for(i=2;i<N;i++)g[i]+=g[i-1];
}
int main()
{
	ll n,m,i,j,ans;
	scanf("%lld",&T);EU();
	while(T--)
	{
		scanf("%lld%lld",&n,&m);ans=0;
		for(i=1;i<=n&&i<=m;i=j+1)
		{
			j=min(n/(n/i),m/(m/i));
			ans+=(n/i)*(m/i)*(g[j]-g[i-1]);
		}
		printf("%lld\n",ans);
	}
}