题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5726
给你n个数，q个询问，每个询问问你有多少对l r的gcd(a[l] , ... , a[r]) 等于的gcd(a[l'] ,..., a[r'])。
先用RMQ预处理gcd，dp[i][j] 表示从i开始2^j个数的gcd。
然后用map存取某个gcd所对应的l r的数量。
我们可以在询问前进行预处理，先枚举i，以i为左端点的gcd(a[i],..., a[r])的种类数不会超过log2(n)，gcd呈单调不增性。(因为gcd值每次变化，至少除以2)
所以所有的gcd的种类个数最多就nlog2(n)。
明白之后，我们可以枚举i为左端点固定，然后二分一下右端点，计算每种gcd的数量。
大概理解之后就可以敲了，然后就是细节问题。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define Fill(x, y) memset((x), (y), sizeof(x))
#define Rep(i, x, y) for(int i = x; i <= y; ++i)
#define Dow(i, x, y) for(int i = x; i >= y; --i)
typedef long long LL;
typedef pair <int, int> P;
typedef pair <LL, LL> PLL;
const LL mod = 1e9 + ;
const LL inf = 1e18;
const int N = 1e5 + ;
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
} int dp[N][];
map <int , LL> mp; void ST(int n) {
for(int k = ; k < ; ++k) {
for(int i = ; i + ( << k) - <= n ; ++i) {
dp[i][k] = GCD(dp[i][k - ] , dp[i + ( << (k - ))][k - ]);
}
}
} int rmq(int l , int r) {
int k = log2(r - l + );
return GCD(dp[l][k] , dp[r - ( << k) + ][k]);
} int main()
{
int t , n , q , u , v;
scanf("%d" , &t);
for(int ca = ; ca <= t ; ++ca) {
scanf("%d" , &n);
for(int i = ; i <= n ; ++i)
scanf("%d" , &dp[i][]);
ST(n);
mp.clear();
for(int i = ; i <= n ; ++i) {
int l , r , temp = i , gcd = dp[i][] , s = i;
do {
l = temp , r = n;
s = l , gcd = rmq(i , s);
while(l <= r) {
int mid = (l + r) / ;
temp = mid;
if(rmq(i , mid) < gcd) {
r = mid - ;
temp = mid - ;
}
else {
l = mid + ;
}
}
mp[gcd] += (LL)(temp - s + );
temp++;
}while(temp <= n);
}
printf("Case #%d:\n" , ca);
scanf("%d" , &q);
while(q--) {
scanf("%d %d" , &u , &v);
int gcd = rmq(u , v);
printf("%d %lld\n" , gcd , mp[gcd]);
}
}
return ;
}