GCD（ST+二分）

GCD

题意：给出一个数列，m次询问，每次询问 l，r区间内的gcd值和与该区间gcd值相同的区间有多少个

思路：枚举每一个左端点，找每个左端点对应的所有gcd值区间，预处理出来，由于gcd值呈阶梯下降，所以完全可以处理，此时顺便用map统计区间个数一开始考虑的是用线段树取gcd值，在加上二分处理，但是发现这样做其实复杂度达到了 t*n*logn*logn*logn ，直接T掉，然后想到用RMQ O（1）去处理gcd值，降下一个logn成功AC

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <functional>
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn=100010;
11 const int inf=0x3f3f3f3f;
12 int n;
13 int a[maxn];
14 int st[maxn][30];
15 int Log2[maxn];
16 
17 int Gcd(int a,int b){
18     return b==0?a:Gcd(b,a%b);
19 }
20 
21 /***************ST打表*******************************/
22 void init(){                        //预处理
23     for(int i=0;i<=n;i++){
24         if(i==0){
25             Log2[i]=-1;
26         }
27         else{
28             Log2[i]=Log2[i>>1]+1;
29         }
30     }
31     for(int j=1;(1<<j)<=n;j++){
32         for(int i=1;i+(1<<j)<=n+1;i++){
33             st[i][j]=Gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
34         }
35     }
36 }
37 
38 int query(int l,int r){             //询问l~r之间数的gcd
39     int k=Log2[r-l+1];
40     return Gcd(st[l][k],st[r-(1<<k)+1][k]);
41 }
42 
43 /****************二分*********************************/
44 map<int,ll>cnt;
45 void Binary(int i){                 //二分找从i开始往后的所有gcd,因为数(不同的数)越多,gcd越小,gcd单调不递增,就可以用二分了
46     int l,r,ri,le,v;
47     l=i;                            //一开始走右边界都是i
48     r=i;
49     while( r<=n ){
50         le=r;                       //右边界的最左
51         ri=n;                       //右边界的最右,为二分右边界的位置做准备
52         v=query(l,r);               //求出一开始的l~r的gcd
53         while(le<=ri){              //二分找gcd==v的最右端,这样最右端到l之间的数只能使val保持与l~r之间的gcd相同
54             int mid=(le+ri)>>1;
55             if(query(l,mid)==v){
56                 le=mid+1;
57             }
58             else ri=mid-1;
59         }
60         cnt[v]+=le-r;
61         r=le;
62     }
63 }
64 
65 int main()
66 {
67     int t,q,v;
68     int cas=1;
69     scanf("%d",&t);
70     while( t-- ){
71         scanf("%d",&n);
72         for(int i=1;i<=n;i++){
73             scanf("%d",&a[i]);
74             st[i][0]=a[i];
75         }
76         init();
77         cnt.clear();
78         for(int i=1;i<=n;i++){
79             Binary(i);
80         }
81         scanf("%d",&q);
82         printf("Case #%d:
",cas++);
83         for(int j=0;j<q;j++){
84             int x,y;
85             scanf("%d%d",&x,&y);
86             v=query(x,y);
87             printf("%d %lld
",v,cnt[v]);
88         }
89     }
90     return 0;
91 }