【Bzoj2301】【Luogu2522】Problem_b

来源和评测点

HAOI2011
Bzoj2301
Luogu2522
Caioj1282

题目

【题目大意】
对于给出的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
100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000
【输出格式】
共n行,每行一个整数表示满足要求的数对(x,y)的个数
【输入样例】
2
2 5 1 5 1
1 5 1 5 2
【输出样例】
14
3

分析

莫比乌斯教程和题目分类参见:
【OI之路】11更高级数论-2莫比乌斯
其他莫比乌斯题目参见:Tag-莫比乌斯

嗯这次就不能硬搞了,会超时哒(bzoj上51000+到11000ms),所以要分块了
而且还要用到容斥,因为下界也是变量了,画张图就灰常好理解了

至于分块,如下:
采用前缀和优化+分块思想
因为(n/d)*(m/d)有连续的一段是相等的,
所以对莫比乌斯函数计算前缀和

代码

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
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
//************************定义************************
typedef long long ll;
const int MAXNUM=100000,MAXPR=10000;
int mu[MAXNUM+10];
//************************线性筛************************
bool prv[MAXNUM+10];
int prime[MAXPR+10],pr;
void getmu()
{
pr=0;memset(prv,1,sizeof(prv));
mu[1]=1;
for(int i=2;i<=MAXNUM;i++)
{
if(prv[i]==1)
{
prime[++pr]=i;
mu[i]=-1;
}
for(int j=1;j<=pr;j++)
{
ll t=ll(i)*ll(prime[j]);
if(t>ll(MAXNUM)) break;
prv[t]=0;
if(i%prime[j]==0)
{
mu[t]=0;
break;
}
else mu[t]=-mu[i];
}
mu[i]+=mu[i-1];
}
}
//************************主函数************************
ll calc(int n,int m)
{
if(n>m) swap(n,m);
ll ans=0;
int t=1;
//F[d]=sigma[ f(t) ] d|t
//f(t)=sigma[ mu(d/t)*F[d] ] t|d
int last=0;
for(int i=1;i<=n;i=last+1)//i=d/t
{
int d=i*t;
last=mymin( n/(n/d) , m/(m/d) );
ans+=ll(mu[last]-mu[i-1])*ll(n/d)*ll(m/d);
}
return ans;
}
int main()
{
getmu();
int n;scanf("%d",&n);
for(int tk=1;tk<=n;tk++)
{
int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0)
{
printf("0\n");
continue;
}
a=(a-1)/k,b=b/k,c=(c-1)/k,d=d/k;
printf("%lld\n",calc(b,d)-calc(b,c)-calc(a,d)+calc(a,c));
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/12b6.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%