Steven_MengのBlog

考虑$g_1=gcd(a_l,a_{l+1},…,a_{r}),g_2=gcd(a_l,a_{l+1},…,a_r,a_{r+1})$

显然有$g_1$为$g_2$的倍数

若$g_1!=g_2$,那么肯定$g_2 \le \fra\dfrac}{2}$

这就说明我们固定$l$,$gcd$的不同值至多有$\log _2 a[l]$种。

于是我们用$ST$表维护$gcd$值,每次可以二分到$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
77
#include <bits/stdc++.h>
#define MAXN 300005
#define MAXM 35
#define int long long
using namespace std;
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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n;
int q[MAXN],a[MAXN];
map<int,int>ans;
namespace ST_table{
int st[MAXM][MAXN],lg[MAXN];
inline void Init_ST(){
lg[0]=-1;
for (register int i=1;i<=n;++i){
lg[i]=lg[i>>1]+1;
}
for (register int i=1;i<=n;++i){
st[0][i]=a[i];
}
for (register int i=1;i<MAXM;++i){
for (register int j=1;j+(1<<i)-1<=n;++j){
st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
}
inline int Query(int l,int r){
if (l>r) return 0;
int k=lg[r-l+1];
return __gcd(st[k][l],st[k][r-(1<<k)+1]);
}
}
using namespace ST_table;
inline int Find(int L,int p,int g){
int l=p,r=n,ans=0;
while (l<=r){
int mid=(l+r)>>1;
if (Query(L,mid)==g) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
inline int Calc(int p){
int now=a[p],L=p;
while (true){
int lst=p;
p=Find(L,p,now);
ans[now]+=p-lst+1;
if (p==n) return 0;
++p;
now=Query(L,p);
}
}
#undef int
int main(){
#define int long long
n=read();
for (register int i=1;i<=n;++i) a[i]=read();
int m=read();
for (register int i=1;i<=m;++i) q[i]=read();
Init_ST();
for (register int i=1;i<=n;++i) Calc(i);
for (register int i=1;i<=m;++i){
printf("%I64d\n",ans[q[i]]);
}
}

 评论