题意：动态查询区间的gcd，和gcd的值的个数。
分析：gcd的查找可以线段树，val(node) = gcd(val(left),val(val))，我是用ST表搞的。
然后查询这个值的区间有多少个。
简单说就是，这个gcd 不会很多，可以分区间hash好。
二分写的很糟。
#include <bits/stdc++.h>using namespace std;const int maxn = 100000+5;int n; int a[maxn]; int d[maxn][20];int gcd(int a,int b) {return b==0 ? a : gcd(b,a%b); }void init(int* a) {for(int i=0; i<n; i++)d[i][0] = a[i];for(int j=1; (1<<j)<=n; j++)for(int i=0; i+(1<<j)-1<n; i++)d[i][j] = gcd(d[i][j-1],d[i+(1<<(j-1))][j-1]); }int sol(int L,int R) {int k = 0;while(1<<(k+1)<=R-L+1) k++;return gcd(d[L][k],d[R-(1<<k)+1][k]); }int main() {//freopen("in.txt","r",stdin);int t;scanf("%d",&t);int kase = 1;while(t--){scanf("%d",&n);for(int i=0; i<n; i++)scanf("%d",&a[i]);init(a);map<int,long long> rec;for(int i=0; i<n; i++){int g = d[i][0],L=i;while(L<n){int l = L;int r = n;g = sol(i,L);while(l<r){if(r-l==1) {if(sol(i,r)==g&&r!=n) {l = r;break;}else break;}int mid = l+(r-l)/2;int tmp = sol(i,mid);if(tmp==g)l = mid;else r = mid-1;}//printf("%d %d\n",l,l-L+1);rec[g] += (l-L)+1;L = l+1;}}printf("Case #%d:\n",kase++);int q;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);l--;r--;int tmp = sol(l,r);printf("%d %I64d\n",tmp,rec[tmp]);}}return 0; }