HDU 5726 (RMQ 二分)

題目連結：點選這裡

題意：每次詢問一個區間的gcd，和這個gcd相同的區間的個數。

區間的gcd個數最多不會超過 log(max) 個， 而且gcd序列又是遞減的，是以直接暴力枚舉左端點，對右端點二分求出每一個值的區間扔到map裡面統計一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
#define maxn 100005
#define mod 1000000007

int dp[maxn][];
int a[maxn];
int n, q;
map <int, long long> gg;

int scan () {
    char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    int x=;
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    return x;
}

void rmq_init () {
    for (int i = ; i < n; i++) dp[i][] = a[i];
    for (int j = ; (<<j) <= n; j++) {
        for (int i = ; i+(<<j)- < n; i++) {
            dp[i][j] = __gcd (dp[i][j-], dp[i+(<<(j-))][j-]);
        }
    }
}

int rmq (int l, int r) {
    int k = ;
    while ((<<(k+)) <= r-l+) k++;
    return __gcd (dp[l][k], dp[r-(<<k)+][k]);
}

void solve () {
    for (int i = ; i < n; i++) {
        int pos = n-;
        while (pos >= i) { 
            int tmp = rmq (i, pos);
            int l = i, r = pos;
            while (r-l > ) {
                int mid = (l+r)>>;
                if (rmq (i, mid) == tmp) r = mid;
                else l = mid;
            }
            int cur;
            if (rmq (i, l) == tmp) cur = l;
            else cur = r;
            gg[tmp] += (pos-cur+);
            pos = cur-;
        }
    }
}

int main () {
    int t, kase = ;
    scanf ("%d", &t);
    while (t--) {
        printf ("Case #%d:\n", ++kase);
        gg.clear ();
        n = scan ();
        for (int i = ; i < n; i++) a[i] = scan (); 
        rmq_init ();
        solve (); 
        q = scan ();
        while (q--) {
            int l = scan (), r = scan ();
            int ans = rmq (l-1, r-1);
            printf ("%d %lld\n", ans, gg[ans]);
        }
    }
    return ;
}