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

A,the length of

A is

n
Let

f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)

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

n
Second line has

n integers

Ai
Third line has one integers

Q,the number of questions
Next there are Q lines,each line has two integers

1≤T≤3

1≤n,Q≤104

1≤ai≤109

1≤l<r≤n

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;
}