HAOI2011 problem b

发表于 | 分类于

HAOI2011 problem b

题目描述

对于给出的$n$个询问，每次求有多少个数对$(x,y)$，满足$a≤x≤b，c≤y≤d$，且$gcd(x,y) = k，gcd(x,y)$函数为x和$y$的最大公约数。

输入输出格式

输入格式：

第一行一个整数n，接下来n行每行五个整数，分别表示$a、b、c、d、k$

输出格式：

共$n$行，每行一个整数表示满足要求的数对$(x,y)$的个数

输入输出样例

输入样例#1：

2
2 5 1 5 1
1 5 1 5 2

输出样例#1：

14
3

说明

$100%$的数据满足：$1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000$

莫比乌斯反演

借着这道题谈一下莫比乌斯反演

莫比乌斯函数

莫比乌斯函数是一个积性函数

其定义如下
$$\mu(n)=\begin{cases}
1,n=1\\
(-1)^k=p_1p_2…p_k,p_i\in{prime}\\
0,else
\end{cases}$$

莫比乌斯函数具有以下性质
$$\sum_{d|n}\mu(d)=\begin{cases}
1,n=1\\
0,n>1
\end{cases}$$

莫比乌斯函数是积性函数

Dirichlet卷积

两个数论函数$f(x),g(x)$的卷积$(f×g(x))$定义为
$$f×g(n)=\sum_{d|n}f(d)g(\frac n d)$$

莫比乌斯反演

如果数论函数$f(x),g(x)$满足
$$f(n)=\sum_{d|n} g(d)$$
那么它们也满足
$$g(n)=\sum_{d|n}\mu(n)f(\frac n d)$$

题解

显然上面那一题就是一个比较裸的莫比乌斯反演题了

首先来看如果去掉$x,y$的下限

首先两边同时除以$k$

那么条件就变成了
$$gcd({\frac x k},{\frac y k})=1$$.

而且有
$$\sum_{d|n}\mu(d)=[n=1]$$
原来要求的是
$$\sum_{x=a}^b\sum_{y=c}^d[gcd(x,y)=k]$$
就转化为了
$$\sum_{x=1}^{b’}\sum_{y=1}^{d’}\sum_{d|(x,y)}\mu(d)$$
然后
显然就是一个除法之后向下取整求和

但是直接枚举$d$就TLE了

于是采用分块处理

但是很显然有下限，于是容斥原理
(画下图就知道了。。。)

code

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
int check[50005],mu[50005],p[50005],sum[50005];
void Getmobius()
{
	memset(check,0,sizeof(check));
	mu[1]=1;
	int tot=0;
	for(int i=2;i<=50000;i++)
	{
		if (!check[i])
		{
			p[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot;j++)
		{
			if (i*p[j]>50000) break;
			check[i*p[j]]=1;
			if (i%p[j]==0)
			{
				mu[i*p[j]]=0;
				break;
			}
			else mu[i*p[j]]=-mu[i];
		}
	}
	sum[0]=0;
	for(int i=1;i<=50000;i++)
		sum[i]=sum[i-1]+mu[i];
}
LL Calc(int a,int b)
{	
	LL ans=0LL;
	int pos;
	for(int d=1;d<=min(a,b);d=pos+1)
	{
		pos=min(a/(a/d),b/(b/d));
		ans+=(LL)(sum[pos]-sum[d-1])*(a/d)*(b/d);
	}
	return ans;
}
int main()
{
        Getmobius();
	int T;
	scanf("%d",&T);
	while (T--)
	{
		int a,b,c,d,k;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		a=(a-1)/k,b/=k,c=(c-1)/k,d/=k;
		LL ans=0LL;
		ans=Calc(b,d)-Calc(a,d)-Calc(c,b)+Calc(a,c);
		printf("%lld\n",ans);
	}
	return 0;
}