GCD/center>
题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5726
Description
Give you a sequence of N(N≤100,000) integers : a1,...,an(0<ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤l<r≤N)such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Input
The first line of input contains a number T, which stands for the number of test cases you need to solve.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a1,...,an(0<ai≤1000,000,000).
The third line contains a number Q, denoting the number of queries.
For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
Output
For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).
For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
Sample Output
Case #1:
1 8
2 4
2 4
6 1
Hint
题意
给你n个数，Q次询问，问你(l,r)区间的gcd是多少，然后再问你整个序列中，有多少子串的gcd和询问的GCD是相同的。
题解：
线段树TLE了，应该是我们写丑了……
然后改成了倍增RMQ才过的。
考虑gcd这个东西，枚举起点后，他最多log(1e9)种可能，所以我们直接枚举起点，然后暴力二分到每个gcd的区间，然后直接算这个gcd的贡献。
那么我们的询问就都可以O（1）回答了。
代码
#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 15;
int N,a[maxn],b[maxn][18],mm[maxn];
map < int , long long > ha;
void initrmp(int n)
{
mm[0]=-1;
for(int i=1;i<=n;i++){
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
}
}
int query(int l,int r){
int k = mm[r-l+1];
return __gcd(b[l][k],b[r-(1<<k)+1][k]);
}
int main(int argc,char *argv[]){
int T=read(),cas=0;
while(T--){
ha.clear();
N=read();
initrmp(N);
rep(i,1,N){
a[i]=read();
b[i][0]=a[i];
}
rep(j,1,17) for(int i = 1 ; i + ( 1 << j ) - 1 <= N ; ++ i) b[i][j]=__gcd( b[i][j-1] , b[i + two(j-1)][j-1] );
rep(i,1,N){
int cur = i , gc = a[i];
while( cur <= N ){
int l = cur , r = N;
while( l < r ){
int mid = l + r + 1 >> 1;
if(query(i,mid)==gc) l = mid ;
else r = mid - 1;
}
if(ha.count(gc)) ha[gc] +=(l-cur+1);
else ha[gc]=(l-cur+1);
cur = l + 1 , gc = __gcd( gc , a[l + 1] );
}
}
int Q=read();
pf("Case #%d:\n",++cas);
while(Q--){
int l = read(),r=read(),gc=query(l,r);
pf("%d",gc);
if(ha.count(gc)) pf(" %I64d\n",ha[gc]);
else pf(" 0\n");
}
}
return 0;
}