本文主要是介绍2016 Multi-University Training Contest 1-1004---HDU 5726 GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：HDU 5726
题意：给出一串数，对于每次区间查询输出这个区间的GCD，并且统计共有多少个区间的GCD等于这个GCD值。
题解：
区间GCD查询：线段树。
统计区间个数：首先，在统计某个区间的GCD值时，相当于统计最后一个数和前面所有数的 GCD 的GCD。
用一个map ans来记录全局的GCD区间个数，map中key为GCD值，value为等于这个值得区间个数。
枚举区间上界，用一个map来记录到连续到当前位置（上界为当前位置）的各GCD区间个数，用当前map （上次循环的结果，每次循环完成要用一个中间变量来存储）中的GCD与当前位置的值求GCD，将map累加更新至全局ans。最后直接输出即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int MAX=100000+10;
typedef long long LL;
int a[MAX];
int sum[MAX<<2];
int m;map<int,LL> ans;//全局
map<int,LL> map1;//中间变量
map<int,LL> map2;void PushUP(int root)
{ sum[root] = __gcd(sum[root<<1], sum[root<<1|1]);
} void build(int root, int left, int right)
{ if (left == right) { sum[root] = a[m++]; return; } int middle = (left + right) >> 1; build(root << 1, left, middle); build(root << 1|1, middle + 1, right); PushUP(root);
} int Query(int L, int R, int root, int left, int right)
{ if (L <= left && right <= R) { return sum[root]; } int m = (left + right) >> 1; int ret = 0; if (L <= m) ret = __gcd(ret, Query(L, R, root << 1, left, m)); if (R > m) ret = __gcd(ret, Query(L, R, root << 1|1, m + 1, right)); return ret;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);int tcase=1;while(t--){int n;scanf("%d",&n);ans.clear();map1.clear();map2.clear();for(int i=1;i<=n;i++){scanf("%d",&a[i]);}m=1;build(1,1,n);ans[a[1]]++;map1[a[1]]++;for(int i=2;i<=n;i++){map2[a[i]]++;ans[a[i]]++;for(map<int,LL>::iterator it=map1.begin();it!=map1.end();it++){int next=__gcd(a[i],it->first);map2[next]+=it->second;ans[next]+=it->second;}map1.clear();map1=map2;map2.clear();}printf("Case #%d:\n",tcase++);int k;scanf("%d",&k);for(int i=1;i<=k;i++){int l,r;scanf("%d%d",&l,&r);int gcd=Query(l,r,1,1,n);printf("%d %I64d\n",gcd,ans[gcd]);}}return 0;
}这篇关于2016 Multi-University Training Contest 1-1004---HDU 5726 GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
