Different GCD Subarray Query

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

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 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

Recommend

wange2014

长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.

树状数组满足这种操作，但是知道这个我也不会啊，不懂后来那种统计操作

#include<bits/stdc++.h>

using namespace std;

const int N=;

int c[N],a[N],n,Q,last[N*],ans[N];

vector < pair<int,int> >q[N],b[N];

void add(int k,int num) {

    while(k<=n) {

        c[k]+=num;

        k+=k&-k;

    }

}

int read(int k) {

    int res=;

    while(k) {

        res+=c[k];

        k-=k&-k;

    }

    return res;

}

int main() {

    while(~scanf("%d%d",&n,&Q)) {

        for(int i=; i<=n; i++) {

            scanf("%d",&a[i]);

            q[i].clear();

            b[i].clear();

        }

        for(int i=; i<=n; i++) {

            int x=a[i],y=i;

            b[i].push_back(make_pair(x,y));

            for(int j=; j<b[i-].size(); j++) {

                int t=b[i-][j].first;

                y=b[i-][j].second;

                int g=__gcd(t,a[i]);

                if(g!=x) {

                    b[i].push_back(make_pair(g,y));

                    x=g;

                }

            }

        }

        for(int i=; i<=Q; i++) {

            int L,R;

            scanf("%d%d",&L,&R);

            q[R].push_back(make_pair(L,i));

        }

        memset(c,,sizeof(c));

        memset(last,,sizeof(last));

        for(int i=; i<=n; i++) {

            for(int j=; j<b[i].size(); j++) {

                int x = b[i][j].first,y= b[i][j].second;

                if(last[x])

                    add(last[x],-);

                last[x] = y;

                add(y,);

            }

            for(int j=; j<q[i].size(); j++) {

                int x=q[i][j].first,y=q[i][j].second;

                ans[y]=read(i)-read(x-);

            }

        }

        for(int i=; i<=Q; i++) printf("%d\n",ans[i]);

    }

    return ;

}

巴特西

树状数组 gcd 查询 Different GCD Subarray Query

Different GCD Subarray Query

最新文章

热门文章