BigHead
0%

HDU 5726 GCD (16多校第一场)

Posted on Edited on In , Views: Valine:

题意

$给你一个长度为n(1\leq n \leq 100000)序列:a _1,a _2, a_3…(1 \leq a _i \leq 10 ^9 )$
$现在给你q个查询,每个查询问你存在多少个区间gcd的值等于区间[l,r]区间的gcd值$

分析

  • 第一步使用倍增可以很快求出区间[l,r]的gcd的值
  • 如何很快的统计有多少个区间的gcd值等于x?

$这里需要认识到一个性质,以某一个数字开始往后gcd的值只会减少不会增加,因而最多有log _2 x$
$所以这里我们可以记录以某一个位置开始或结束所有区间gcd的状态即可$
$eg: dp[i]记录以位置i结尾所有区间gcd的值以及个数$
$则有dp[i+1]=dp[i]+gcd(dp[i],a[i+1])$

刚开始以为不能用map,后面直接map过了,使用map映射转移的话复杂度是nlog$ ^2 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/*************************************************************************
	> File Name: d.cpp
	> Author: liangxianfeng
	> Mail:   liangxianfeng96@qq.com
	> Created Time: 2016年07月19日 星期二 17时52分44秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x <<  endl; 
const int maxn = 2e6+100;
const int INF = 0x3f3f3f3f;
const int HASHSIZE = 1e5+7;

int a[maxn];
const int N = 60;

int n, m;
int gcd(int x, int y){
    if(y==0) return x;
    return  gcd(y, x%y);
}
int sum[maxn];
void build(int rt, int l, int r){
    if(l == r){
        scanf("%d", &a[l]);
        sum[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(rt<<1, l, m);
    build(rt<<1|1, m+1, r);
    sum[rt] = gcd(sum[rt<<1], sum[rt<<1|1]);
}
int query(int rt, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr){
        return sum[rt];
    }
    int m = (l + r) >> 1;
    if(qr <= m) return query(rt<<1, l, m, ql, qr);
    else if(ql > m) return query(rt<<1|1, m+1, r, ql, qr);
    else{
        return gcd(query(rt<<1, l, m, ql, qr), query(rt<<1|1, m+1, r, ql, qr));
    }
}
int l[maxn], r[maxn];
int num[maxn], ans[maxn];
map<int, ll> ha, mp[2];
int dp[20][123456];
int getlen(int x){
    int ans = 0;
    while(x){
        ans++;
        x>>=1;
    }
    return ans;
}
int main(){
#ifdef LOCAL
	freopen("/home/zeroxf/桌面/in.txt","r",stdin);
	//freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int t;
    scanf("%d", &t);
    int kase = 0;
    while(t--){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i){
            scanf("%d", &dp[0][i]);
        }
        for(int i = 1; (1<<i)<=n; ++i){
            for(int j = 1; j <= n; ++j){
                dp[i][j] = gcd(dp[i-1][j], dp[i-1][j+(1<<(i-1))]);
            }
        }
        scanf("%d", &m);
        int x, y;
        for(int i = 0; i < m; ++i){
            scanf("%d%d", &x, &y);
            int len = getlen(y-x+1) -1;
            num[i] = gcd(dp[len][x], dp[len][y-(1<<len)+1]);
        }
        int now = 0, pre = 1;
        mp[0].clear();
        mp[1].clear();
        ha.clear();
        for(int i = 1; i <= n; ++i){
            swap(now,pre);
            mp[now].clear();
            for(auto itr = mp[pre].begin(); itr != mp[pre].end(); itr++){
               int temp = gcd(dp[0][i], itr->first);
               mp[now][temp] += itr->second;
            }
            mp[now][dp[0][i]]++;
            for(auto itr = mp[now].begin(); itr != mp[now].end(); itr++){
                ha[itr->first] += itr->second;
            }

        }
        printf("Case #%d:\n",++kase);
        for(int i = 0; i < m; ++i){
            //prln(num[i]);
            printf("%d %lld\n", num[i], ha[num[i]]);
        }
        
    }
	return 0;
}