首页 > 代码库 > 2016 ACM/ICPC Asia Regional Dalian Online 1002/HDU 5869

2016 ACM/ICPC Asia Regional Dalian Online 1002/HDU 5869

2024-08-13 04:25:40   218人阅读

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

 

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
 

 题意：

 题解：

 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 __int6415 #define pii pair<int,int>16 #define MP make_pair17 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) const28   {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 }

 

2016 ACM/ICPC Asia Regional Dalian Online 1002/HDU 5869


联系
我们