HDU 5726 GCD（RMQ+二分）

http://acm.split.hdu.edu.cn/showproblem.php?pid=5726

题意：
给出一串数字，现在有多次询问，每次询问输出（l,r）范围内所有数的gcd值，并且输出有多少数量区间的gcd值等于该gcd值。

思路：

第一问的话可以用线段树或RMQ来解决，RMQ的话简单点。

有意思的是第二问，假设我们现在固定左端点，那么往右端扩大区间时，gcd单调不增，并且每次至少减少一倍，所以我们可以二分枚举。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 1e5 + 5;
16 
17 int n;
18 int a[maxn];
19 int d[maxn][50];
20 
21 map<int,ll> ans;
22 
23 int gcd(int a, int b)
24 {
25     return b==0?a:(gcd(b,a%b));
26 }
27 
28 void init()
29 {
30     for(int i=0;i<n;i++)  d[i][0]=a[i];
31     for(int j=1;(1<<j)<=n;j++)
32         for(int i=0;i+(1<<j)-1<n;i++)
33             d[i][j]=gcd(d[i][j-1],d[i+(1<<(j-1))][j-1]);
34 }
35 
36 int query(int L, int R)
37 {
38     int k = 0;
39     while((1<<(k+1)) <= R-L+1)  k++;
40     return gcd(d[L][k],d[R-(1<<k)+1][k]);
41 }
42 
43 int main()
44 {
45     //freopen("in.txt","r",stdin);
46     int T;
47     int kase = 0;
48     scanf("%d",&T);
49     while(T--)
50     {
51         printf("Case #%d:
",++kase);
52         scanf("%d",&n);
53         for(int i=0;i<n;i++)  scanf("%d",&a[i]);
54         ans.clear();
55         init();
56         for(int i=0;i<n;i++)
57         {
58             int j=i, g=a[i];
59             while(j<n)
60             {
61                 int l=j,r=n-1;
62                 while(l<r)
63                 {
64                     int mid=(l+r)>>1;
65                     if(query(l,r)==g)  l=mid+1;
66                     else r=mid-1;
67                 }
68                 ans[g]+=l-j+1;
69                 j=l+1;
70                 g=gcd(g,a[j]);
71             }
72 
73         }
74         int q; scanf("%d",&q);
75         while(q--)
76         {
77             int l,r;
78             scanf("%d",&l);scanf("%d",&r);
79             int g=query(l-1,r-1);
80             printf("%d %lld
",g,ans[g]);
81         }
82     }
83     return 0;
84 }