首页 > 代码库 > HDU 5726 GCD（DP）

HDU 5726 GCD（DP）

2024-08-21 07:02:52   220人阅读

 

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5726

 

【题目大意】

　　给出数列An，对于询问的区间【L，R】，求出区间内数的GCD值，并且求出GCD值与其相等的区间总数

 

【题解】

　　首先，固定一个区间的右端点，利用GCD的递减性质，可以求出GCD相等的区间左端点的范围，将其范围的左右端点保存下来，同时，对于每个新产生的区间，以其GCD值为下标的MAP值+1，最后对于每个询问，在其右端点保存的范围中查找，获得其GCD值，同时在MAP中获取该GCD值对应的区间总数，输出即可。

 

【代码】

#include <map>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;map<int,long long> M;const int N=100005;int Gcd,n,l[N],v[N],len[N],T,j,q,L,R,Cas,a[N];struct data{int l,v;}p[N][50];int gcd(int x,int y){return __gcd(x,y);}int main(){    scanf("%d",&T);    while(T--){        printf("Case #%d:\n",++Cas);        M.clear();        scanf("%d",&n);        memset(len,0,sizeof(len));        for(int i=1;i<=n;i++)scanf("%d",&a[i]);        for(int i=1;i<=n;i++)for(v[i]=a[i],j=l[i]=i;j;j=l[j]-1){            v[j]=gcd(v[j],a[i]);            while(l[j]>1&&gcd(a[i],v[l[j]-1])==gcd(a[i],v[j]))l[j]=l[l[j]-1];            p[i][len[i]].l=l[j];p[i][len[i]++].v=v[j];            M[v[j]]+=(j-l[j]+1);        }scanf("%d",&q);        while(q--){            scanf("%d%d",&L,&R);            for(int i=0;i<len[R];i++){                if(L>=p[R][i].l){Gcd=p[R][i].v;break;}            }printf("%d %lld\n",Gcd,M[Gcd]);        }    }return 0;}

　　

HDU 5726 GCD（DP）


联系
我们