HDU 5726 GCD (16多校第一场)

题意

$给你一个长度为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;
}