首页 > 代码库 > hdu 5381 The sum of gcd 莫队+预处理

hdu 5381 The sum of gcd 莫队+预处理

2024-09-13 23:06:47   221人阅读

The sum of gcd

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


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 l,r
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
251 2 3 4 531 32 31 444 2 6 931 32 42 3
 

 

Sample Output
9616182310
 

 

Author
SXYZ
 

 

Source
2015 Multi-University Training Contest 8
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5381
题意：一句话题意；
思路：首先莫队离线处理，式必须的；
　　　然后重点就在于如何更新那个变化的值；
　　　根据取模的性质，每次取模最少/2；
　　　gcd也是同理；
　　　也就是说区间的gcd不同数的个数最多不超过log（n）个；
　　　这样就可以更新了；
　　　开始我写了一个RMQ，每次二分查找每一段，超时了；
　　　然后学到一个预处理的姿势；
　　　预处理见代码init那段；
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e4+10,M=4e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;///   数组大小int a[N];int n,pos[N],k;vector<pair<int,int> >l[N],r[N];struct is{    int l,r,now;    bool operator <(const is &b)const    {        if(pos[l]!=pos[b.l])            return pos[l]<pos[b.l];        return r<b.r;    }}p[N];ll out[N],ans;void prex(int L,int R,int flag){    ll sum=0;    int p=L;    for(int i=0;i<l[L].size();i++)    {        int k=min(R,l[L][i].first);        if(k>=p)        sum+=1LL*(k-p+1)*l[L][i].second;        if(k>=R)break;        p=k+1;    }    if(flag==1)ans+=sum;    else ans-=sum;}void nexx(int L,int R,int flag){    ll sum=0;    int p=R;    for(int i=0;i<r[R].size();i++)    {        int k=max(r[R][i].first,L);        if(p>=k)        sum+=1LL*(p-k+1)*r[R][i].second;        if(k<=L)break;        p=k-1;    }    if(flag==1)ans+=sum;    else ans-=sum;}void init(){    for(int i=1;i<=n;i++)        l[i].clear(),r[i].clear();    ans=0;    // 预处理l    l[n].push_back(make_pair(n,a[n]));    for(int i=n-1;i>=1;i--)    {        int g=a[i];        int p=i;        for(int j=0;j<l[i+1].size();j++)        {            int k=__gcd(g,l[i+1][j].second);            if(g!=k)l[i].push_back(make_pair(p,g));            g=k;            p=l[i+1][j].first;        }        l[i].push_back(make_pair(p,g));    }    //预处理r    r[1].push_back(make_pair(1,a[1]));    for(int i=2;i<=n;i++)    {        int g=a[i];        int p=i;        for(int j=0;j<r[i-1].size();j++)        {            int k=__gcd(g,r[i-1][j].second);            if(g!=k)r[i].push_back(make_pair(p,g));            g=k;            p=r[i-1][j].first;        }        r[i].push_back(make_pair(p,g));    }}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        k=sqrt(n);        for(int i=1; i<=n; i++)            scanf("%d",&a[i]),pos[i]=(i-1)/k+1;        init();        int q;        scanf("%d",&q);        for(int i=1; i<=q; i++)            scanf("%d%d",&p[i].l,&p[i].r),p[i].now=i;        sort(p+1,p+1+q);        int L=1,R=0;        for(int i=1; i<=q; i++)        {            while(L<p[i].l)            {                prex(L,R,0);                L++;            }            while(L>p[i].l)            {                L--;                prex(L,R,1);            }            while(R>p[i].r)            {                nexx(L,R,0);                R--;            }            while(R<p[i].r)            {                R++;                nexx(L,R,1);            }            out[p[i].now]=ans;        }        for(int i=1; i<=q; i++)            printf("%lld\n",out[i]);    }    return 0;}

 

 

hdu 5381 The sum of gcd 莫队+预处理


联系
我们