HDU 5726 GCD(RMQ+2分)(線分樹も可)

Give you a sequence of N(N≤100,000) integers : a1,...,an(0

The first line of input contains a number T, which stands for the number of test cases you need to solve.

The first line of each case contains a number N, denoting the number of integers.

The second line contains N integers, a1,...,an(0

For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).

    rmq     rmq      （         。。。）；

     gcd     1              ；

         L，   R   ， map      ；

#include 
#define rep(i,j,k) for(int i = j; i <= k; i++)
#define LL long long
using namespace std;
int n, m;
int f[100010][18];
int a[100010];
map<int, LL>mp;
int gcd(int a, int b) {return b?gcd(b,a%b):a;}
void rmq(){
    rep(i,1,n) f[i][0] = a[i];
    rep(j,1,17)
        rep(i,1,n)
            if(i+(1<1 <= n)
                f[i][j] = gcd(f[i][j-1], f[i+(1<1)][j-1]);
}
int ser(int l, int r){
    int k = (int)log2((double)(r - l + 1));
    return gcd(f[l][k],f[r-(1<1][k]);
}
void setTable(){
    mp.clear();
    rep(i,1,n){
        int g = f[i][0],j = i;
        while(j <= n){
            int l = j, r = n;
            while(l < r){
                int mid = (l+r+1)>>1;
                if(ser(i, mid) == g) l = mid;
                else r = mid - 1;
            }
            mp[g] += l-j+1;
            j = l + 1;
            g = ser(i,j);
        }
    }
}
int main(){
    int t, l, r;
    int cas = 1;
    cin >> t;
    while(t--){
        cin >> n;
        rep(i,1,n) scanf("%d", a+i);
        rmq();
        setTable();
        cin >> m;
        printf("Case #%d:
", cas++);
        rep(i,0,(m-1)){
            scanf("%d%d", &l, &r);
            int tmp = ser(l, r);
            printf("%d %I64d
", tmp, mp[tmp]);
        }
    }
    return 0;
}