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

 

 

Recommend

wange2014

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

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

#include
      
       using namespace std;const int N=200005;int c[N],a[N],n,Q,last[N*10],ans[N];vector < pair
       
         >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=0;    while(k) {        res+=c[k];        k-=k&-k;    }    return res;}int main() {    while(~scanf("%d%d",&n,&Q)) {        for(int i=1; i<=n; i++) {            scanf("%d",&a[i]);            q[i].clear();            b[i].clear();        }        for(int i=1; i<=n; i++) {            int x=a[i],y=i;            b[i].push_back(make_pair(x,y));            for(int j=0; j