HDU5726 GCD（March. 2nd, 2019） 二分查找 特殊技巧

// La Pluie
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ln;
const int N = 1e5 + 5;
int dp[N][21], log[N];
map <int, ln> v;
inline int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;
}
inline int st(int l, int r){
    int d = log[r - l + 1];
    return gcd(dp[l][d], dp[r - (1 << d) + 1][d]);
}
int main(){
    int T, n, q, cnt = 0;
    scanf("%d", &T);
    while(T--){
        v. clear();
        scanf("%d", &n); log[0] = -1;
        for(int i = 1; i <= n; i++)
            scanf("%d", &dp[i][0]), log[i] = log[i >> 1] + 1;
        for(int j = 1; j <= log[n]; j++)
            for(int i = 1; i <= n; i++)
                if(i + (1 << j - 1) <= n) dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
        for(int i = 1; i <= n; i++){
            int L = i, R = i; // 区间[L,R]为扩展区间，即在原区间[i,L]外扩展出的区间。初始为[i,i]。
            while(R <= n){
                int l = L, r = n, g = st(i, L); // 由于最大公因数随数字的变多而只减不增，并且最大公因数相同段被尽量长地统计，所以如果把所有g输出来，必呈降序。
                while(l <= r){
                    int mid = (l + r) >> 1;
                    if(st(i, mid) == g) l = mid + 1;
                    else r = mid - 1;
                }
                R = l;
                v[g] += (ln)R - L; // 增加的区间分别为[i,L],[i,L+1],[i,L+2],……,[i,R]。此处的R实际上是下一个扩展区间的起点，并且v[g]加上的应该是：    真正的R    - L + 1。由于下一扩展区间的起点是    真正的R    + 1，所以此处就代换掉了。
                L = R;
            }
        }
        printf("Case #%d:\n", ++cnt);
        scanf("%d", &q);
        while(q--){
            int l, r;
            scanf("%d %d", &l, &r);
            int g = st(l, r);
            printf("%d %lld\n", g, v[g]);
        }
    }
    return 0;
}