The sum of gcd

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1156 Accepted Submission(s): 508

Problem Description

You have an array

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
First line has one integers

Output

For each question,you need to print

f(l,r)

Sample Input

   2 5 1 2 3 4 5 3 1 3 2 3 1 4 4 4 2 6 9 3 1 3 2 4 2 3  

Sample Output

   9 6 16 18 23 10  

【题意】如题所示。

【解题方法】gcd预处理套莫队算法。大牛博客http://blog.csdn.net/u014800748/article/details/47680899

【AC 代码】

//
//Created by just_sort 2016/9/12 16:50
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e4+7;
int n,m,block;
int a[maxn];
LL ans[maxn];
struct Q{
    int l,r,id;
    bool operator<(const Q &rhs) const{
        if(l/block==rhs.l/block) return r<rhs.r;
        return l/block<rhs.l/block;
    }
}q[maxn];
struct node{int id;int g;};
vector <node> vl[maxn],vr[maxn];
void init(){
    for(int i=1; i<=n; i++){
        if(i==1) vl[i].push_back(node{i,a[i]});
        else{
            int curg=a[i];
            int L=i;
            for(auto &it:vl[i-1]){
                int g = __gcd(it.g,curg);
                if(g!=curg) vl[i].push_back(node{L,curg});
                curg=g,L=it.id;
            }
            vl[i].push_back(node{L,curg});
        }
    }
    for(int i=n; i>=1; i--){
        if(i==n) vr[i].push_back(node{i,a[i]});
        else{
            int curg=a[i];
            int R=i;
            for(auto &it:vr[i+1]){
                int g = __gcd(it.g,curg);
                if(g!=curg) vr[i].push_back(node{R,curg});
                curg=g,R=it.id;
            }
            vr[i].push_back(node{R,curg});
        }
    }
}
LL cal(int op,int L,int R)
{
    LL ret = 0;
    if(op==0){
        int tr = R;
        for(auto &it : vl[R]){
            if(it.id>=L){
                ret += 1LL*(tr-it.id+1)*it.g;
                tr = it.id-1;
            }else{
                ret += 1LL*(tr-L+1)*it.g;
                break;
            }
        }
    }else{
        int tl = L;
        for(auto &it : vr[L]){
            if(it.id<=R){
                ret += 1LL*(it.id-tl+1)*it.g;
                tl = it.id+1;
            }else{
                ret += 1LL*(R-tl+1)*it.g;
                break;
            }
        }
    }
    return ret;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) vl[i].clear(),vr[i].clear();
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        init();
        scanf("%d",&m);
        for(int i=0; i<m; i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        block = (sqrt(n));
        sort(q,q+m);
        int L=1,R=0;
        LL ret = 0;
        for(int i=0; i<m; i++){
            while(R<q[i].r){
                R++;
                ret += cal(0,L,R);
            }
            while(R>q[i].r){
                ret -= cal(0,L,R);
                R--;
            }
            while(L>q[i].l){
                L--;
                ret += cal(1,L,R);
            }
            while(L<q[i].l){
                ret -= cal(1,L,R);
                L++;
            }
            ans[q[i].id] = ret;
        }
        for(int i=0; i<m; i++){
            printf("%I64d\n",ans[i]);
        }
    }
    return 0;
}