[原创]HDU 5726 GCD [ST表+暴力二分]【数据结构|杂类】

2017-01-24 17:26:37 Tabris_ 阅读数：305

博客爬取于2020-06-14 22:41:57
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54709231

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5726
-----------------------------------------------------------------------.
GCD

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3164 Accepted Submission(s): 1146

Problem Description
Give you a sequence of N(N≤100,000) integers : a1,…,an(0 < ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,al+1,…,ar) and count the number of pairs(l′,r′)(1≤l< r≤N)such that gcd(al′,al′+1,…,ar′) equal gcd(al,al+1,…,ar).

Input
The first line of input contains a number T, which stands for the number of test cases you need to solve.

The first line of each case contains a number N, denoting the number of integers.

The second line contains N integers, a1,…,an( 0 < ai ≤ 1000,000,000).

The third line contains a number Q, denoting the number of queries.

For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.

Output
For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,…,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,…,ar′) equal gcd(al,al+1,…,ar).

Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4

Sample Output
Case #1:
1 8
2 4
2 4
6 1

Author
HIT
-----------------------------------------------------------------------.
题目大意:
有一个长度为N的序列,Q次查询,每次查询需求解出gcd{A},A={ai∣i∈[l,r]}gcd\{A\}, A=\{a_i|i\in[l,r]\}及与区间gcd值相同的区间有多少个.

解题思路
首先对与区间gcd 我们可以用线段树或者ST表预处理下,因为没有元素更改,相比之下后者更好(复杂度上,代码量上)

然后就是如何就解与区间gcd值相同的区间有多少个.
这个我们只能枚举一端,然后向右找,然后用个map来存储结果,这样的话复杂度是O(n2)O(n^2),显然不可取.
但是对于一个区间上的gcd来说一定是不增的.这样就有了单调性,我们就可以二分做了,但这样需要三层循环解决.,而且在枚举不同端点的时候还会有重复统计的情况.
然后考虑,一个gcd的递减的过程最多也就这能递减因子数个,那么我们每一次记录的就是一种gcd值的区间,然后接下来串过来就好了,

最后的复杂度就是O(n∗因子个数∗二分)O(n*因子个数*二分)

附本题代码
-----------------------------------------------------------------------.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 100000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
inline int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
/***********************************************************************/
int n;
int a[N];
int st[N][20],mm[N];
void ST(){
    for(int j=1;(1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void initrmp(int x){
    mm[0]=-1;
    for(int i=1;i<=x;i++)    mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
}

int getST(int l,int r){
    int k=mm[r-l+1];
    return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
map<int ,LL> ans;
int main(){
    initrmp(100000);
    int _,kcase;
    while(~scanf("%d",&_)){
        kcase = 0;
        while(_--){
            ans.clear();
            n=read();
            for(int i=1;i<=n;i++)    a[i]=read(),st[i][0]=a[i];
            ST();
            for(int i=1;i<=n;i++){
                int cur = i , gc = a[i];
                while( cur <= n ){
                    int l = cur , r = n;
                    while( l < r ){
                        int mid = l + r + 1 >> 1;
                        if(getST(i,mid)==gc) l = mid ;
                        else r = mid - 1;
                    }
                    if(ans.count(gc)) ans[gc] +=(l-cur+1);
                    else ans[gc]=(l-cur+1);
                    cur = l + 1 , gc = gcd( gc , a[l + 1] );
                }
            }

            int q;
            q=read();
            printf("Case #%d:\n",++kcase);
            while(q--){
                int l=read(),r=read(),g=getST(l,r);
                printf("%d %I64d\n",g,ans[g]);
            }
        }
    }
    return 0;
}