The sum of gcd

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 23    Accepted Submission(s): 4

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

9

6

16

18

23

10

求一个区间内随意子区间的gcd之和。

分析：

对于区间[l,r]求gcd之和的复杂度是nlog(n)的

：：

如果处理了[l,r]的结果，那么对于[l,r+1]。能产生的新的子区间为[r-l+1]个。怎样合并？

由于增加r+1，那么[L,r+1]，（l<=L<=r)必定都是经过r位置的。知道r与之前每一个位置的gcd。

用num[r+1]与这些gcd值，做gcd得到新的gcd值，就是全部新子区间的gcd结果。对于每一个gcd乘以相应的

区间个数就可以。

当然越往左。gcd就会越小，而且最多出现log个gcd值。把同样的gcd合并就能降低运算量。

然后新增加的数自己能够成为一个区间，增加答案中。

处理的复杂度是nlog的，由于分块了，

长度为n的最多sqrt(n)段，复杂度是nlog(n)*sqrt(n)

在块内。长度是sqrt(n)且最多次计算。全部是qlog(n)*sqrt(n)==================（log(n)是gcd的种类数）

如今处理合并两段了：

由于分成左右两段，例如以下

原序列：1 1 1 2 2  2  4 4 4| 4 4 4 2 2 2 1 1 1 （|是分隔位置）

gcd：1 1 1  2 2 2  4 4 4 | 4 4 4 2 2 2 1 1 1

gcd计算的该点到切割位置的路径的gcd，由于合并肯定是须要经过切割位置的！

显然能够知道gcd的种类仅仅有 log(n)个。对于左边的每一个gcd和右边的每一个gcd做一下gcd函数。然后乘以左边该段

的长度*右边该段的长度。如样例就是

gcd(1,1)*3*3+gcd(1,2)*3*3 + gcd(1,4)*3*3)...........+....

怎样计算得到每一个gcd相应的区间个数呢？

能够知道从分隔线到两边的gcd是递减的。假设g是[l,r]的gcd，那么对于[l-1,r]仅仅要gcd(g,num[l-1])就计算出来了

然后得到的gcd假设与g同样就和并。否则增加一个新值。

复杂度分析：

对于每段，求出全部gcd和个数是o(n)的。

长的一段最多求sqrt(n)次。是n*sqrt(n)的。短的是sqrt(n)*q次

合并时复杂度是q*log(n)*log(n)的，所以是 O(sqrt(n)*n+q*sqrt(n)+q*log(n)*log(n))

接下来看代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define maxn 20001

#define ll long long

int gcd(int a,int b){

    if(b == 0) return a;

    return gcd(b,a%b);

}

ll ans[maxn];

struct Node{

    int l,r,id;

};

Node que[maxn];

int length;//分块排序函数

int comp(Node a,Node b){

    if(a.l / length == b.l / length)

        return a.r < b.r;

    return a.l /length < b.l/length;

}

int num[maxn];

struct Point{

    int g,num;

    Point(int _g=0,int _n=0):g(_g),num(_n){}

};

vector<Point> lgcd;

vector<Point> ltrgcd;

vector<Point> rgcd;

vector<Point> rtlgcd;

int main(){

    int t,n,q;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i = 0;i < n; i++)

            scanf("%d",num+i);

        scanf("%d",&q);

        for(int i = 0;i < q; i++){

            scanf("%d%d",&que[i].l,&que[i].r);

            que[i].id = i;

            que[i].l--,que[i].r--;

        }

        for(length = 1; length * length < n; length++);

        sort(que,que+q,comp);//按快排序，同一个块内r从小到大排序

        memset(ans,0,sizeof(ans));

        lgcd.clear();

        rgcd.clear();

        ltrgcd.clear();

        rtlgcd.clear();

        int RR = -1,kuai = -1,j,k,l,LL;

        ll res = 0,resl = 0;

        Point a;

        for(int i = 0;i < q; i++){ 处理每一个询问

            if(kuai != que[i].l/length){//新块。所以长的一段要重头開始处理

                kuai = que[i].l/length;

                rtlgcd.clear();

                rgcd.clear();

                RR = kuai*length+length-1;

                res = 0;

            }

            while(RR < que[i].r){

                RR++;//处理分隔线到RR的gcd之和。

for( j = 0;j < rgcd.size(); j++){

                    rgcd[j].g = gcd(rgcd[j].g,num[RR]);

                    res += (ll)rgcd[j].g*rgcd[j].num;

                }

                rgcd.push_back(Point(num[RR],1));

                res += num[RR];

                for(j = 0,k = 1;k<rgcd.size();k++){

                    if(rgcd[j].g == rgcd[k].g){

                        rgcd[j].num += rgcd[k].num;

                    }

                    else {

                        j++;

                        rgcd[j] = rgcd[k];

                    }

                }

                while(rgcd.size() > j+1) rgcd.pop_back();//合并同样的gcd

                 //处理分隔线到每一个RR的gcd个数

                if(rtlgcd.size() == 0)

                    rtlgcd.push_back(Point(num[RR],1));

                else {

                    k = rtlgcd.size()-1;//仅仅需比較最小的那个gcd就可以。即最右边计算得到的gcd

                    a.g = gcd(rtlgcd[k].g,num[RR]);

                    a.num = 1;

                    if(a.g == rtlgcd[k].g)

                        rtlgcd[k].num++;

                    else rtlgcd.push_back(a);

                }

            }

            LL = kuai*length+length-1;

            lgcd.clear();

            ltrgcd.clear();

            resl = 0;//左边的处理与右边的一样

            LL = min(LL,que[i].r);

            for(;LL >= que[i].l; LL--){

                for(j = 0;j < lgcd.size(); j++){

                    lgcd[j].g = gcd(lgcd[j].g,num[LL]);

                    resl += (ll)lgcd[j].g*lgcd[j].num;

                }

                lgcd.push_back(Point(num[LL],1));

                resl += num[LL];

                for(j = 0,k=1;k<lgcd.size();k++){

                    if(lgcd[j].g == lgcd[k].g){

                        lgcd[j].num += lgcd[k].num;

                    }

                    else {

                        j++;

                        lgcd[j] = lgcd[k];

                    }

                }

                while(lgcd.size() > j+1) lgcd.pop_back();

                if(ltrgcd.size() == 0){

                    ltrgcd.push_back(Point(num[LL],1));

                }

                else {

                    k = ltrgcd.size()-1;

                    a.g = gcd(ltrgcd[k].g,num[LL]);

                    a.num = 1;

                    if(a.g == ltrgcd[k].g)

                        ltrgcd[k].num++;

                    else ltrgcd.push_back(a);

                }

            }//合并两个区间

            ans[que[i].id] = res + resl;

            int id = que[i].id,gg;

            for(j = 0;j < ltrgcd.size(); j++){

                gg = ltrgcd[j].g;

                for(k = 0;k < rtlgcd.size(); k++){

                    gg = gcd(gg,rtlgcd[k].g);

                    ans[id] += (ll)gg*ltrgcd[j].num*rtlgcd[k].num;

                }

            }

        }

        for(int i = 0;i < q; i++){

            printf("%I64d\n",ans[i]);

        }

    }

    return 0;

}