1. 首页
2. RMQ, 二分
3. 本页

HDU 5726 GCD (RMQ+二分)

题目链接：点我~~

题意：给你n个数，m个询问，每次询问某个区间，求这段区间所有数的gcd，然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~

思路：对于求区间gcd可以用线段树维护，或者RMQ，因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd，考虑枚举左端点，二分区间进行预处理~例如12467，以1为左端点，1~5为右端点5个gcd都是1，其实只要算一次就可以了，然后看以这个为左端点的区间有哪些值，并且把区间长度算出来就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 100100;

int d[MAXN<<2];
int dp[MAXN][30];
int mm[MAXN];
int a[MAXN];

void intRMQ(int n,int b[])
{
    mm[0]=-1;
    for(int i=1; i<=n; ++i)
    {
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        dp[i][0]=b[i];
    }
    for(int j=1; j<=mm[n]; ++j)  //for(int j=1;(1<<j)<=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 x,int y)
{
    int k=mm[y-x+1];
    return __gcd(dp[x][k],dp[y-(1<<k)+1][k]);
}

map<int,LL > mp;

int main()
{
    int n,t,q;
    scanf("%d",&t);
    int casee=1;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        intRMQ(n,a);
        mp.clear();
        for(int i=1; i<=n; ++i)
        {
            int l=i;
            int r=i;
            while(r<=n)
            {
                int ll=r;
                int rr=n;
                int tmp=rmq(i,ll);
                while(ll<=rr)
                {
                    int mid=(ll+rr)>>1;
                    if(rmq(i,mid)==tmp)
                    {
                        ll=mid+1;
                    }
                    else
                    {
                        rr=mid-1;
                    }
                }
                mp[tmp]+=ll-r;
                r=ll;
            }
        }
        scanf("%d",&q);
        printf("Case #%d:\n",casee++);
        for(int i=1; i<=q; i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int gd=rmq(l,r);
            printf("%d %lld\n",gd,mp[gd]);
        }

    }
    return 0;

}