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