GCD (RMQ + 二分)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int maxn = 1e5 + 7;
int in[maxn], dp[maxn][21], mm[maxn];
map<int, LL>cnt;

void init(int n){
    mm[0] = -1;
    for(int i = 1; i <= n; i ++){
        mm[i] = (i&(i - 1))?mm[i - 1]:mm[i - 1] + 1;
        dp[i][0] = in[i];
    }
    for(int j = 1; j <= mm[n]; j ++)
        for(int i = 1; i + (1<<j) - 1 <= n; i ++)
            dp[i][j] = __gcd(dp[i][j - 1], dp[i + (1<<(j-1))][j - 1]);
}

int RMQ(int l, int r){
    int k = mm[r - l + 1];
    return __gcd(dp[l][k], dp[r - (1<<k) + 1][k]);
}

int main(){
    int T,n,m;scanf("%d",&T);
    for(int ncase = 1; ncase <= T; ncase ++){
        printf("Case #%d:
",ncase);
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++)scanf("%d",&in[i]);
        init(n);cnt.clear();
        int L, R, l, r, val, m;
        for(int i = 1; i <= n; i ++){
            cnt[in[i]] ++;
            L = i;R = n;
            while(L < R){
                val = RMQ(L,R) + 1;
                l = L;r = R;
                while(l < r){
                    m = (l + r)/2;
                    if(RMQ(L, m) >= val)
                        l = m + 1;
                    else
                        r = m;
                }
                cnt[val - 1] += R - m;
                R = m;
            }
        }
        scanf("%d",&m);
        for(int i = 0; i < m; i ++){
            scanf("%d%d",&l,&r);
            int val = RMQ(l,r);
            printf("%d %lld
",val, cnt[val]);
        }
    }
    return 0;
}