hdu 5869 Different GCD Subarray Query BIT+GCD 2016ICPC 大连网络赛 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

Input

There are several tests, process till the end of input.

For each test, the first line consists of two integers

Output

For each query, output the answer in one line.

Sample Input

5 3 1 3 4 6 9 3 5 2 5 1 5

Sample Output

6 6 6

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 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define CT continue
#define SC scanf
const 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
",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 大连网络赛 Different GCD Subarray Query

相关推荐