HDU 5726 GCD （线段树维护区间gcd）

HDU 5726 GCD （线段树维护区间gcd）

GCD

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2445    Accepted Submission(s): 855

Problem Description

Give you a sequence of N(N≤100,000) integers : a1,...,an(0

Input

The first line of input contains a number T, which stands for the number of test cases you need to solve. The first line of each case contains a number N, denoting the number of integers. The second line contains N integers, a1,...,an(0

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1). For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).

Sample Input

1 5 1 2 4 6 7 4 1 5 2 4 3 4 4 4

Sample Output

Case #1: 1 8 2 4 2 4 6 1

Author

HIT

Source

​​2016 Multi-University Training Contest 1​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5775​​​ ​​5774​​​ ​​5773​​​ ​​5772​​​ ​​5771​​

题解：给你n个数,然后有 m个询问，每个询问一个区间，问你这个区间的GCD是多少，并且问你从1到n有多少个区间的GCD和这个区间的GCD是相同的。

AC代码：

#includeusing namespace std; typedef long long ll; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 mapmp; const int N=1e5+7; int n,i,j,a[N],l[N],v[N],tr[N<<2]; using namespace std;void init(){ mp.clear(); scanf("%d",&n); 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]; mp[v[j]] += j - l[j] + 1; } } void build(int l=1,int r=n,int rt=1){ if(l==r){ tr[rt]=a[l]; return; } int m=(l+r)>>1; build(lson); build(rson); tr[rt]=__gcd( tr[rt<<1] , tr[rt<<1|1]); } int query(int L,int R,int l=1,int r=n,int rt=1){ if(L<=l&&r<=R) return tr[rt]; int m=(l+r)>>1; if(R<=m) return query(L,R,lson); if(L>m) return query(L,R,rson); return __gcd(query(L,R,lson) , query(L,R,rson)); } int main(){ int t; int x,y,k; int cas= 1; scanf("%d",&t); while(t--) { init(); build(); scanf("%d",&k); printf("Case #%d:\n",cas++); while(k--) { scanf("%d%d",&x,&y); int ans = query(x,y); printf("%d %lld\n",ans,mp[ans]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。