首页 > 代码库 > hdu 5869 Different GCD Subarray Query BIT+GCD 2016ICPC 大连网络赛

hdu 5869 Different GCD Subarray Query BIT+GCD 2016ICPC 大连网络赛

2024-08-13 06:29:51   221人阅读

Different GCD Subarray Query

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 828    Accepted Submission(s): 300


Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:
  
  Given an array a of N positive integers a1,a2,?aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,?,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
  
 

 

Input
There are several tests, process till the end of input.
  
  For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.

You can assume that 
  
    1≤N,Q≤100000 
    
   1≤ai≤1000000
 

 

Output
For each query, output the answer in one line.
 

 

Sample Input
5 31 3 4 6 93 52 51 5
 

 

Sample Output
666
 

 

Source
2016 ACM/ICPC Asia Regional Dalian Online

 题意：有n个数字依次存放在一个数组中(n<=1e5),每个数字<=1e6,数组中每个子序列可以产生一个整个子序列的最大公约数，有q个询问(q<=1e5)，每次询问包括两个数字，l,r询问下标从l,到r的区间内一共有多少个不同的GCD；

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <iostream>#include <cmath>#include <map>#include <stack>#include <queue>#include <vector>#include <bitset>#include <set>#define MM(a,b) memset(a,b,sizeof(a));#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;#define CT continue#define SC scanfconst int N=1e5+10;int n,qur,a[N],tree[N],ans[N],pos[10*N];struct node{   int l,id;};int gcd(int a,int b){   if(b==0) return a;   else return gcd(b,a%b);}int lowbit(int i){   return i&(-i);}int add(int pos,int val){    while(pos<=n){        tree[pos]+=val;        pos+=lowbit(pos);    }}int query(int r){    int s=0;    while(r>=1){        s+=tree[r];        r-=lowbit(r);    }    return s;}vector<node> q[N],lgcd[N];void solve(){    for(int i=1;i<=n;i++){        if(pos[a[i]]!=-1) add(pos[a[i]],-1);        pos[a[i]]=i;        add(i,1);        int val=a[i];        for(int j=i-1;j>=1;j--){           int k=gcd(val,a[j]);           if(pos[k]<j){              if(pos[k]!=-1) add(pos[k],-1);              pos[k]=j;              add(j,1);           }           if(k==1) break;           val=k;        }        for(int j=0;j<q[i].size();j++){            int l=q[i][j].l,id=q[i][j].id;            ans[id]=query(i)-query(l-1);        }    }}int main(){    while(~SC("%d%d",&n,&qur)){       MM(tree,0);       MM(pos,-1);       for(int i=1;i<=n;i++) {          SC("%d",&a[i]);          q[i].clear();       }       for(int i=1;i<=qur;i++) {           int l,r;           SC("%d%d",&l,&r);           q[r].push_back((node){l,i});       }       solve();       for(int i=1;i<=qur;i++) printf("%d\n",ans[i]);    }    return 0;}

　　分析：

错因分析：比赛的时候想到了每个数字的gcd并不会很多，，但是想到的解决方法是，先统计出从1到i（1<=i<=n）的各个位置所拥有的gcd种类数，，然后对于一个区间[l,r]，用种类数r-种类数l-1，，，，但是这样有个很显然的错误就是[l,l-1]内出现的gcd有可能在[l,r]内再次出现，所以这样肯定就错了

纠正与解答：对于这样的问题，

1.我们可以从1-n依次固定右端点，然后从i向前扫，得到一个gcd，然后用BIT维护其gcd最靠右位置，在BIT中+1(可以想象，固定右端点后，越靠右，则不管怎样的区间，都尽可能包含)

2.最多在loga时间内gcd衰减至1.复杂度nlogn*logn;

hdu 5869 Different GCD Subarray Query BIT+GCD 2016ICPC 大连网络赛


联系
我们