欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【hdu5726 2016 Multi-University Training Contest 1 】(区间gcd+线段树/st好题)

程序员文章站 2022-05-12 23:32:03
...

链接:http://acm.hdu.edu.cn/showproblem.php?pid=5726

题意:多组数据,给n个数,给出一个询问l,r,查找在所有子区间中,能够等于[l,r]的区间gcd的数的个数。

思路:首先我们需要求出每个子区间中的区间gcd.(由于区间的可加性,明显满足线段树维护的特点,可以通过线段树来求出每个子区间的区间gcd),并且,对于区间gcd而言,以a[i]为结尾的区间gcd的gcd为以a[i-1]为结尾的区间gcd与a[i]。完成了所有区间的求gcd后,由于大量的查询,并且对于每个a,其因子不超过log(a)个,所以暴力预处理一下每个gcd的区间个数。实现方式,可以用map完成映射。

题目特性:

1.区间的可加性———线段树维护求解所有区间信息

2.计数所有区间中满足某个特性的个数————通过转移递推式,两者之间的关系来完成,设法减小复杂度(n*n->nlog(n)),双指针移动,中间变量map保存。

代码:

//gcd性质:数字ai最多有log2(ai)个质因子
#include<cstdio>
#include<math.h>
#include<string.h>
#include<queue>
#include<map>
#include<math.h>
#include<iostream>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x));
#define pi acos(-1.0)
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll powmod(ll a ,ll b,ll mod){ll ans=1;while(b){if(b%2)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;}
const int maxn=100000+7;
ll a[maxn];
map<ll,ll>cnt,mp1,mp2;
map<ll,ll>::iterator it;

struct node{
	int l,r;
	int v;
}t[maxn];

void build(int i,int L,int R){
	t[i].l=L;t[i].r=R;
	if(L==R){
		t[i].v=a[L];
	}
	else{
		int mid=(L+R)/2;
		build(i*2,L,mid);build(i*2+1,mid+1,R);
		t[i].v=gcd(t[i*2].v,t[i*2+1].v);
	}
}

ll query(int i,int L,int R){
	if(t[i].l==L&&t[i].r==R){
		return t[i].v;
	}
	if(R<=t[i*2].r) return query(i*2,L,R);
	else if(L>=t[i*2+1].l)return query(i*2+1,L,R);
	else{
		int mid=(t[i].l+t[i].r)/2;
		return gcd(query(i*2,L,mid),query(i*2+1,mid+1,R));
	}
}
int main(){
	int t;
	scanf("%d",&t);
	int ca=1;
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		build(1,1,n);
		mp1.clear ();
		mp2.clear ();
		cnt.clear ();
		for(int i=1;i<=n;i++){
			cnt[a[i]]++;
			mp2[a[i]]++;
			for(it=mp1.begin ();it!=mp1.end ();it++){
				int k=gcd(it->first ,a[i]);
				cnt[k]+=it->second ;
				mp2[k]+=it->second ;
			}
			mp1.clear ();
			for(it=mp2.begin ();it!=mp2.end();it++){
				mp1[it->first ]=it->second ;
			}
			mp2.clear ();
		}

		int q;
		scanf("%d",&q);
		printf("Case #%d:\n",ca++);
		while(q--){
			int l,r;
			scanf("%d%d",&l,&r);
			ll ans=query(1,l,r);
			printf("%lld %lld\n",ans,cnt[ans]);
		}
	}
}

相关标签: 好题 线段树