HDU 5726 RMQ+二分

題意

給一堆數，問任意一段區間的GCD。并且求出有多少個區間和這個區間的GCD相等。

題解

求區間的GCD很好求，把模闆套上去就可以了。至于多少個區間的GCD相等，暴力肯定是不行的，那樣的話，ST算法就失去意義了。因為長區間的GCD一定小于或等于短區間的GCD，是以可以二分求取。

對于i<=j<=k，必然存在一段區間使得gcd(i,j)==gcd(i,k)。因為gcd(i,j)>=gcd(i,k)恒成立，是以可以二分求取區間k。可以明顯看出k-j+1這個長度的區間内所有的gcd(i,x)都是等于gcd(i,j)的，記錄一下就可以了。

最後查詢的時候，把剛才記錄的值直接輸出就可以了。

代碼

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 800010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;

int d[][];
int n;
int a[];
map<int,LL> mp;

int gcd(int x,int y) {
    if(y==)
        return x;
    return gcd(y,x%y);
}

void rmq_init() {
    UP(i,,n) {
        d[i][]=a[i];
//        cout<<d[i][0]<<endl;
    }
    for(int j=; (<<j)<=n; j++) {
        for(int i=; i+(<<j)-<n; i++) {
            d[i][j]=gcd(d[i][j-],d[i+(<<(j-))][j-]);
        }
    }
}

int rmq(int l,int r) {
    int k=;
    W((<<(k+))<=r-l+)
    k++;
    return gcd(d[l][k],d[r-(<<k)+][k]);
}

int main() {
    int t,q;
    scanf("%d",&t);
    int ks=;
    W(t--) {
        printf("Case #%d:\n",ks++);
        mp.clear();
        MEM(d,);
        MEM(a,);
        scanf("%d",&n);
        UP(i,,n) {
            scanf("%d",&a[i]);
        }
        rmq_init();
        UP(i,,n){
            int ll=i,rr=i;
            W(rr<n){
                int lt=rr;
                int rt=n-;
                int v=rmq(ll,rr);
                W(lt<=rt){
                    int mid=(lt+rt)/;
                    if(rmq(ll,mid)>=v){
                        lt=mid+;
                    }else{
                        rt=mid-;
                    }
                }
                mp[v]+=(lt-rr);
                rr=lt;
            }
        }
        scanf("%d",&q);
        int l,r;
        W(q--) {
            scanf("%d%d",&l,&r);
            int x=rmq(l-,r-);
            printf("%d %I64d\n",x,mp[x]);
        }
    }
}