HDU5726 (GCD)[RMQ，ST算法，二分]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5726

第一问很好做，一个数与它自己的GCD仍是自己，所以区间GCD可以直接用ST表维护。
第二问就比较麻烦了。要做出第二问需要用到几个性质：

  • GCD具有区间单调性（若a<=c<=d<=b，那么GCD(a,b)<=GCD(c,d)）
  • 一个数的因子不超过log(n)个

第一个性质使得二分区间边界成为可能，而有了第二个性质我们就可以枚举每一个左边界，并在这个左边界的前提下尽量向右「扩展」，找到GCD相同的最大的右边界，并把这个GCD下的区间数用map维护；接下来更改GCD（这里GCD是减小了）并继续向右拓展右边界，直到拓展到区间尽头，然后枚举下一个左边界并重复上述步骤。可以证明对于每个左边界，GCD相同的右边界有最多log(n)个（第二个性质）。这样整个初始化过程时间复杂度为O(n * log(n))

这样就统计完了每个GCD对应的区间数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
const int maxn=100009;
int dp[maxn][30];
//int mm[maxn];
int a[maxn];
map<int,long long> M;
int gcd(int a,int b) {
    if(!b) return a;
    return gcd(b,a%b);
}
void initRMQ(int n,int b[]) {
    //mm[0]=-1;
    for(int i=1;i<=n;i++) {
        //mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        dp[i][0]=b[i];
    }
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int x,int y) {
    //int k=mm[y-x+1];
    int k=(int)(log(y-x+1.0)/log(2.0));
    return gcd(dp[x][k],dp[y-(1<<k)+1][k]);
}
int bis(int ll,int rr,int d,int i) {
    int l=ll,r=rr,mid;
    while(l<r) {
        mid=(l+r+1)>>1;
        if(rmq(i,mid)>=d) l=mid;
        else r=mid-1;
    }
    return l;
}
void solve(int l,int r) {
    int d=rmq(l,r);
    long long cnt=M[d];
    printf("%d %lld\n",d,cnt);
}
int main() {
    int T;
    int n,q;
    int l,r;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++) {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        initRMQ(n,a);
        M.clear();

        int d;
        for(int i=1,j,tmp;i<=n;i++) {
            j=i;
            while(j<=n) {
                d=rmq(i,j);
                tmp=bis(j,n,d,i);
                if(M[d]==0) M[d]=tmp-j+1;
                else M[d]+=tmp-j+1;
                j=tmp+1;
            }
        }
        scanf("%d",&q);
        printf("Case #%d:\n",cas);
        for(int i=0;i<q;i++) {
            scanf("%d%d",&l,&r);
            solve(l,r);
        }
    }
    return 0;
}