HDOJ 5726 GCD (16多校day1 1004)

题目传送门

题意:给出n个数,做m次询问。对于所给区间,找出[l,r]的gcd(最大公约数),求出1~n中,区间的gcd与之相等的区间个数。

题解

思路

首先根据数据范围,对于区间的gcd值的维护,考虑线段树或RMQ;

然后,对于所有区间的gcd,我们需要预处理出来。具体实现:考虑枚举左端点,二分区间(注意gcd值单调),算出以这个点为左端点的区间有哪些gcd值,用map记录下相同gcd的区间个数;

相关算法参考

RMQ算法的ST算法 二分

代码

亲测AC

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int Maxn=100000+10;
map <int , long long> Q;
int dp[Maxn][20],a[Maxn],T,n,m;

int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a%b); 
}

void RMQ(int n){ //用RMQ维护区间gcd值; 
    for(int i=1;i<=n;i++) dp[i][0]=a[i];
    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 query(int l,int r){//询问区间gcd值; 
    int tmp=0;
    while((1<<(tmp+1))<=r-l+1) tmp++;
    return gcd(dp[l][tmp],dp[r-(1<<tmp)+1][tmp]);
} 

void solve(){ //二分区间预处理; 
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<=n){
            int l=j,r=n,sum;
            int x=query(i,j);

            while(r>=l){
                int mid=(l+r)>>1;
                if(query(i,mid) == x){
                    sum=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            Q[x]+=sum-j+1;//记录下以x为gcd值的区间个数 
            j=sum+1;
        }
    }
}
int main(){
    //freopen("data.txt","r",stdin);
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        Q.clear();
        memset(dp,0,sizeof(dp));

        RMQ(n);
        solve();    

        scanf("%d",&m);
        printf("Case #%d:\n",k);
        for(int i=1;i<=m;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d %I64d\n",query(l,r),Q[query(l,r)]);
        }

    }
    return 0;
}