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

链接: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]);
		}
	}
}