Description
给数组a1…an,Q个询问，每次询问取决[l, r],问gcd(al…ar)是多少，并且问总共有多少对l’,r’满足gcd(al’…ar’) == gcd(al…ar)
Algorithm
对于问题1,可以用线段树做，每个线段记录这个线段的gcd.但是会超时，所以需要用Sparse-Table做。 具体怎么做，参考《训练指南》P197～198 “RMQ问题”对于问题2,固定左端点的话，gcd(al…ar)是单调不增的。那么每次二分找到最大的一个R,gcd(ai…aR) == gcd(ai…aL)，那么L…R这些都是相同的，用一个map存答案。 查询即可。
Code
#include <bits/stdc++.h>
using namespace std
;
const int N(100000 + 9);
int a
[N
], n
;
int d
[N
][100];
map
<int, long long> ans
;
int mid(int l
, int r
)
{
return l
+(r
-l
)/2;
}
void init()
{
for (int i(1); i
<= n
; i
++) d
[i
][0] = a
[i
];
for (int j(1); (1<<j
) <= n
; j
++)
for (int i(1); i
+(1<<j
) <= n
; i
++)
d
[i
][j
] = __gcd(d
[i
][j
-1], d
[i
+(1<<(j
-1))][j
-1]);
}
int query(int l
, int r
)
{
int k(0);
while ((1<<(k
+1)) <= r
-l
+1) k
++;
return __gcd(d
[l
][k
], d
[r
-(1<<k
)+1][k
]);
}
void solve()
{
scanf("%d", &n
);
for (int i(1); i
<= n
; i
++) scanf("%d", &a
[i
]);
init();
ans
.clear();
for (int i(1); i
<= n
; i
++) {
int L(i
), R(0), g(a
[i
]);
while (L
<= n
) {
int l(L
), r(n
);
while (l
<= r
) {
int m(mid(l
, r
));
if (query(l
, m
) == g
) l
= m
+1, R
= m
;
else r
= m
-1;
}
ans
[g
] += R
-L
+1;
L
= R
+1;
R
= L
;
g
= __gcd(g
, a
[L
]);
}
}
int q
;
scanf("%d", &q
);
while (q
--) {
int l
, r
;
scanf("%d%d", &l
, &r
);
int t(query(l
, r
));
printf("%d %lld\n", t
, ans
[t
]);
}
}
int main()
{
int t
;
scanf("%d", &t
);
for (int i(1); i
<= t
; i
++) {
printf("Case #%d:\n", i
);
solve();
}
}
阅读原文
