当前位置: 首页 > >

hdu 5381 The sum of gcd 莫队算法+区间gcd

发布时间:

题意:



思路:


杰哥说这种题他都做烂了。。。。orz


对于每个a[i]值,我们处理出以a[i]为起点,分别往左边和往右边的gcd区间的情况(gcd区间个数不会超过log(a[i])个,简单解释就是gcd相同的可以合并,且随着区间扩大,若gcd值不同,则每次至少除以2)。


a[i+1]的gcd区间可以由a[i]的情况推出,遇到可以合并的区间(gcd相等)就合并掉。


例如 2 3 3 6 5序列(以往左边gcd区间为例)


a[1] = 2:[1, 1]->2


a[2] = 3:[1, 1]->1,[2, 2]->3


a[3] = 3:[1, 1]->1,[2, 3]->3


a[4] = 6:[1, 1]->1,[2, 3]->3,[4, 4]->6 //[2,3]->3表示这个区间任意一个a[i]到a[4]的区间gcd都等于3


a[5] = 5:[1, 4]->1,[5, 5]->5


(程序中区间顺序是倒过来存储的,这里只是为了方便阅读而写成这样)




最后套用莫队算法,莫队转移时间复杂度为logn


总的复杂度O(nsqrt(n)logn)




code:



#include
using namespace std;

const int N = 1e4+5;
typedef long long LL;

int n, m;
int block;
int a[N];
LL ans[N];
struct PP {
int l, r;
int id;
bool operator < (const PP &cmp) const {
if(l/block == cmp.l/block) return r < cmp.r;
return l/block < cmp.l/block;
}
}q[N];

int gcd(int a, int b) {
return b?gcd(b, a%b):a;
}
struct He {
int idx; //存区间的下标
LL g; //存区间的gcd值
};
vector vl[N], vr[N];
void preDeal() {
//left
//推出左区间gcd的情况
for(int i = 1;i <= n; i++) {
if(i == 1) vl[i].push_back((He){i, a[i]}); //第1个点自己作为区间
else {
int curg = a[i]; //当前的gcd值
int l = i;
for(auto &it:vl[i-1]) {
int tmp = gcd(it.g, curg);
if(tmp != curg) //若gcd不相等,说明这个区间不能和下个区间合并,就可以保存起来了
vl[i].push_back((He){l, curg});
curg = tmp, l = it.idx;
}
vl[i].push_back((He){l, curg}); //把最后一个区间也放进去。
}
}
//right
//推出右区间gcd情况
for(int i = n;i >= 1; i--) {
if(i == n) vr[i].push_back((He){i, a[i]}); //第n个点肯定是自己作为一个区间
else {
int curg = a[i];
int r = i;
for(auto &it:vr[i+1]) {
int tmp = gcd(it.g, curg);
if(tmp != curg)
vr[i].push_back((He){r, curg});
curg = tmp, r = it.idx;
}
vr[i].push_back((He){r, curg});
}
}
}
void solve() {
for(int i = 1;i <= n; i++) vl[i].clear(), vr[i].clear();
block = (int)sqrt(n);
sort(q, q+m);

preDeal();

//莫队算法
int l = 1, r = 0;
LL res = 0;
for(int i = 0;i < m; i++) {
while(r < q[i].r) {
r++;
int tr = r;
for(auto &it:vl[r]) {
if(it.idx >= l) { //区间的idx值比当前的l值要大,说明这整个区间都是符合的,个数减一下就出来了
res += (tr-it.idx+1)*it.g; //下标的计算最好可以自己想仔细点。
tr = it.idx-1;
}
else { //到头了,只能取区间里某一部分。
res += (tr-l+1)*it.g;
break;
}
}
}
while(r > q[i].r) {
int tr = r;
for(auto &it:vl[r]) {
if(it.idx >= l) {
res -= (tr-it.idx+1)*it.g;
tr = it.idx-1;
}
else {
res -= (tr-l+1)*it.g;
break;
}
}
r--;
}
while(l > q[i].l) {
l--;
int tl = l;
for(auto &it:vr[l]) {
if(it.idx <= r) {
res += (it.idx-tl+1)*it.g;
tl = it.idx+1;
}
else {
res += (r-tl+1)*it.g;
break;
}
}
}
while(l < q[i].l) {
int tl = l;
for(auto &it:vr[l]) {
if(it.idx <= r) {
res -= (it.idx-tl+1)*it.g;
tl = it.idx+1;
}
else {
res -= (r-tl+1)*it.g;
break;
}
}
l++;
}
ans[q[i].id] = res;
}
for(int i = 0;i < m; i++) printf("%I64d
", ans[i]);
}

int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1;i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 0;i < m; i++) scanf("%d%d", &q[i].l, &q[i].r);
for(int i = 0;i < m; i++) q[i].id = i;

solve();
}
return 0;
}









友情链接: