BZOJ 2301 【HAOI2011】 Problem b

Description

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

Input

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

Output

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

HINT

100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

  过了这么久终于写出了莫比乌斯反演的入门题TAT……

  这道题主要用到了莫比乌斯函数的一个性质,对于任意正整数$n$,有:$$\sum_{d|n} \mu (d)= \left \{ \begin{aligned} &1 &(n=1) \\ &0 &(n>1) \end{aligned} \right.$$

  所以$[gcd(i,j)=1]$这个式子可以表示为:$$\sum_{d|gcd(i,j)}\mu (d)$$

  于是莫比乌斯反演对于处理$gcd(x,y)=1$这类问题时特别好用。

  莫比乌斯反演戳这里

  本题题解参见黄学长的博客(我已经翻到上一页了……想看本题代码请翻下一篇)

  毕竟我就是看着黄学长的博客做出来的……

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 50010

using namespace std;
typedef long long llg;

int T,a,b,c,d,k,ls;
int mu[maxn],s[maxn],w[maxn];
bool vis[maxn];

int getint(){
	int w=0;bool q=0;
	char c=getchar();
	while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();
	if(c==‘-‘) c=getchar(),q=1;
	while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();
	return q?-w:w;
}

void get(){//线性筛素数与莫比乌斯函数
	mu[1]=1;
	for(int i=2;i<maxn;i++){
		if(!vis[i]) s[++ls]=i,mu[i]=-1;
		for(int j=1;j<=ls && s[j]*i<maxn;j++){
			vis[s[j]*i]=1;
			if(i%s[j]) mu[s[j]*i]=-mu[i];
			else{mu[s[j]*i]=0;break;}
		}
	}
	for(int i=1;i<maxn;i++) w[i]=w[i-1]+mu[i];
}

llg F(int n,int m){//求出x在[1,n]中、y在[1,m]中的答案
	llg ans=0;
	if(n>m) swap(n,m);
	for(int i=1,nt;i<=n;i=nt+1){
		nt=min(n/(n/i),m/(m/i));
		ans+=(llg)(w[nt]-w[i-1])*(llg)(n/i)*(llg)(m/i);
	}
	return ans;
}

int main(){
	File("a");
	get(); T=getint();
	while(T--){
		a=getint(); b=getint(); c=getint();
		d=getint(); k=getint(); a--; c--;//注意边界
		a/=k; b/=k; c/=k; d/=k;
		printf("%lld\n",F(b,d)-F(a,d)-F(b,c)+F(a,c));//转化为前缀和容斥求解
	}
	return 0;
}

  

时间: 10-27

BZOJ 2301 【HAOI2011】 Problem b的相关文章

bzoj2301【HAOI2011】Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 2951  Solved: 1318 [Submit][Status][Discuss] Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数n,接下来n行每行五个整数,分别表示a.b.c.d.k Ou

【BZOJ2301】【HAOI2011】Problem b [莫比乌斯反演]

Problem b Time Limit: 50 Sec  Memory Limit: 256 MB[Submit][Status][Discuss] Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数n,接下来n行每行五个整数,分别表示a.b.c.d.k Output 共n行,每行一个整数表示满足要求的数对(x,y)的个数. Sample Inp

【BZOJ2298】【HAOI2011】problem a 动态规划

链接: #include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/44979323"); } 题解: 一句话 (a,b) 可以理解成一个线段 (a,n?b] . 然后排个序去下重,最后一个线段的权值 x 就是表示 这 x 人互不冲突,一起算. 然后动态规划求若干条不相交线段的权值最大值,最后用总人数减

【HAOI2011】problem a

我的思维能力真的上来了好感动555 原题: 随便点的一道DP题,本来这题以前无数次想不出来,题解好像也看不懂,想的时候都打算放弃了 但是想着一定要死磕思维能力,最后居然还真的自己做出来了 果真是以前放弃得太轻易hhh 首先要确定一下题意,“有ai个人”我感觉也可以理解为>=ai个人 但是其实后来想一下,如果这样说得话就没必要强调可能有相同分数了 因为如果是>=ai的话,两个同分的和两个相邻分数的对于合法性其实都一样 所以认为题意为恰好有ai个人(当然考场上还是大力问监考) 那么研究一下这个约束

【BZOJ2998】Problem A(动态规划)

[BZOJ2998]Problem A(动态规划) 题面 BZOJ 题解 一个人的成绩范围可以确定为一个区间 这样就变成了 选择若干区间,不重合, 每个区间有个权值,求最大权值和 这样就可直接\(dp\)了 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #includ

【HAOI2011】向量

题目描述: 给你一对数a,b,你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量,问你能不能拼出另一个向量(x,y). 说明:这里的拼就是使得你选出的向量之和为(x,y) 输入格式: 第一行数组组数t,(t<=50000) 接下来t行每行四个整数a,b,x,y (-2*10^9<=a,b,x,y<=2*10^9) 输出格式: t行每行为Y或者为N,分别表示可以拼出来,不能拼出来 分析: 我们看

BZOJ 1854 【Scoi2010】 游戏

Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示.当他使用某种装备时,他只能使用该装备的某一个属性.并且每种装备最多只能使用一次. 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害.也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击bo

BZOJ 1303 【CQOI2009】中位数图

baidu了一下bzoj水题列表...找到这道题.   题目大意:给定一个数t,在给定的一段包含1-n的序列中找出多少个长度为奇数子序列的中位数为t. 第一眼没看数据范围,于是开心的打了一个O(n^3)的循环,TLE....   想了想,子序列中必须包含t,所以子序列中其他数的个数必定为偶数,所以子序列中有t以及n个大于t的数和n个小于t的数(n为偶数):   因为是1-n的排列,所以也不会出现多个t的情况..   于是发现了一个很神奇的思路,对于序列里任何一个数,把小于t的数定义为-1,等于t

【bzoj2298】【HAOI2011】【problem a】

2298: [HAOI2011]problem a http://www.lydsy.com/JudgeOnline/problem.php?id=2298 Time Limit: 10 Sec Memory Limit: 256 MB Submit: 696 Solved: 307 [Submit][Status][Discuss] Description 一次考试共有n个人参加,第i个人说:"有ai个人分数比我高,bi个人分数比我低."问最少有几个人没有说真话(可能有相同的分数)