Different GCD Subarray Query
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 681 Accepted Submission(s): 240
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].
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
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
题意：
题解：
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<iostream> 9 #include<cstring> 10 #include<cstdio> 11 #include<map> 12 #include<algorithm> 13 #include<queue> 14 #define LL __int64 15 #define pii pair<int,int> 16 #define MP make_pair 17 const int N=1000006; 18 using namespace std; 19 int gcd(int a,int b) 20 { 21 return b==0 ? a : gcd(b,a%b); 22 } 23 int n,q,a[N],ans[N]; 24 vector<pii> G[N]; 25 struct QQ{ 26 int l,r,id; 27 bool operator < (const QQ &a) const 28 { 29 return a.r>r; 30 } 31 }Q[N]; 32 int C[N],vis[N]; 33 void update (int x,int c) 34 { 35 for(int i=x;i<N;i+=i&(-i)) C[i]+=c; 36 } 37 int ask(int x) 38 { 39 int s=0; 40 for(int i=x;i;i-=i&(-i)) s+=C[i]; 41 return s; 42 } 43 int main() 44 { 45 while(scanf("%d %d",&n,&q)!=EOF) 46 { 47 for(int i=1;i<=n;i++) 48 scanf("%d",&a[i]); 49 for(int i=0;i<=n;i++) 50 G[i].clear(); 51 for(int i=1;i<=n;i++) 52 { 53 int x=a[i]; 54 int y=i; 55 for(int j=0;j<G[i-1].size();j++) 56 { 57 int res=gcd(x,G[i-1][j].first); 58 if(x!=res) 59 { 60 G[i].push_back(MP(x,y)); 61 x=res; 62 y=G[i-1][j].second; 63 } 64 } 65 G[i].push_back(MP(x,y)); 66 } 67 memset(C,0,sizeof(C)); 68 memset(vis,0,sizeof(vis)); 69 for(int i=1;i<=q;i++) 70 { 71 scanf("%d %d",&Q[i].l,&Q[i].r); 72 Q[i].id=i; 73 } 74 sort(Q+1,Q+q+1); 75 for(int R=0,i=1;i<=q;i++) 76 { 77 while(R<Q[i].r) 78 { 79 R++; 80 for(int j=0;j<G[R].size();j++) 81 { 82 int res=G[R][j].first; 83 int ids=G[R][j].second; 84 if(vis[res]) 85 update(vis[res],-1); 86 vis[res]=ids; 87 update(vis[res],1); 88 } 89 } 90 ans[Q[i].id]=ask(R)-ask(Q[i].l-1); 91 } 92 for(int i=1;i<=q;i++) 93 cout<<ans[i]<<endl; 94 } 95 return 0; 96 }