题目描述：给出n( 1 <= n <= 100000)个正整数ai，现给出m(1 <= m <= 100000)个询问，每次询问给出一组L，R，对于每组询问输出LR之间所有数的gcd，并且输出还有多少个区间满足其间所有数的gcd等于LR之间所有数的gcd
思路：这个问题的突破口在于从第i个数开始，连续向后取gcd，其gcd的值是逐渐变小的，且可能出现的gcd的值只有不超过log(ai)个。
那么就从1至n枚举每个位置，找到以i为起点的区间对gcd的贡献，通过上文的分析，以i为起点的区间只会对不超过log(ai)个gcd产生贡献，将他们一一二分出来，然后用map记录下来，在询问当中对于每次LR之间的gcd值可以用st表预处理好，然后O(1)查询，然后从map中找到与这个值相等的区间还有多少个就可以了。
总的复杂度应该是O(Knlogn)，其中K是一个1<=K<=log1e9 的常数
收获：1、过去一直没有重视st表，自己写的时候用线段树O(logn)查询就超时了，st表O(1)查询的能力可以在很多不需修改的RMQ问题中起到不可或缺的作用。
2、其实做题的时候经常想到枚举起点的做法，在网上看到一篇博客枚举终点的做法非常惊艳：
http://blog.csdn.net/helloiamclh/article/details/51979392
#pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #include<bitset> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-6; const int maxn = 1e5 + 5 ; int n,t[4 * maxn] , a[maxn] , d[maxn][33] , klen[maxn]; map<int , LL>mp; inline int gcd(int a , int b) { return b == 0 ? a : gcd(b , a % b); } void RMQ_init() { for(int i = 1 ; i<= n ; i++){ d[i][0] = a[i]; } for(int j = 1 ; (1 << j) <= n ; j++){ for(int i = 1 ; i + (1 << j) - 1<= n ; i++){ d[i][j] = gcd(d[i][j - 1] , d[i + (1<<(j - 1)) ][j - 1]); } } klen[0] = -1; for(int i = 1 ; i<= n ; i++){ klen[i] = ( (i & (i - 1)) == 0 )? klen[i - 1] + 1 : klen[i - 1]; } } int query(int L , int R) { int k = klen[R - L + 1]; return gcd(d[L][k] , d[R - (1<<k) + 1][k]); } int bsearch(int left , int right , int val , int st) { int mid , ret = -1 ; while(left <= right){ mid = left + (right - left) / 2; int q = query(st , mid); if(q >= val){ left = mid + 1; ret = mid; } else{ right = mid - 1; } } return ret; } void solve() { for(int i = 1 ; i <= n ; i++){ int cur = a[i] , pos = i; while(pos <= n){ int ntpos = bsearch(i , n , cur , i); mp[cur]+= (ntpos - pos + 1); if(ntpos == n) break; pos = ntpos + 1; cur = gcd(cur , a[pos]); } } } int main() { int T , m , l , r , kase = 0; scanf("%d", &T); while(T--){ mp.clear(); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } RMQ_init(); solve(); scanf("%d", &m); printf("Case #%d:\n",++kase); for(int i= 1; i<= m ; i++){ scanf("%d %d", &l , &r); int res = query(l , r); LL cnt = mp[res]; printf("%d %lld\n", res , cnt); } } return 0; }