首页 > 代码库 > HDOJ 5381 The sum of gcd 莫队算法

HDOJ 5381 The sum of gcd 莫队算法

2024-09-21 10:05:35   210人阅读


大神题解:

http://blog.csdn.net/u014800748/article/details/47680899


The sum of gcd

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


Problem Description
You have an array ,the length of  is 
Let 
 

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 
Second line has  integers 
Third line has one integers ,the number of questions
Next there are Q lines,each line has two integers ,



 

Output
For each question,you need to print 
 

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
 

Author
SXYZ
 

Source
2015 Multi-University Training Contest 8
 



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=10100;
typedef long long int LL;

struct G
{
    G(){}
    G(int _id,LL _g):id(_id),g(_g){}

    int id;
	LL g;

	void toString()
	{
		printf("id: %d g: %lld\n",id,g);
	}
};

int n,a[maxn],Q;
vector<G> VL[maxn],VR[maxn];
struct Que
{
    int L,R,id;
    bool operator<(const Que& que) const
    {
        if(L!=que.L) return L<que.L;
        return R<que.R;
    }
}que[maxn];

void PreInit()
{
    /// get Left Point
    /// 以i为右端点,预处理出左边的段
    for(int i=1;i<=n;i++)
    {
        VL[i].clear();
        if(i==1)
        {
            VL[i].push_back(G(i,a[i]));
        }
        else
        {
			LL 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(G(L,curg));
				curg=g; L=it.id;
			}
			VL[i].push_back(G(L,curg));
        }
    }
    /// get Right Point
    /// 以i为左端点,预处理出右边的段
	for(int i=n;i>=1;i--)
	{
		VR[i].clear();
		if(i==n)
		{
			VR[i].push_back(G(i,a[i]));
		}
		else
		{
			LL curg=a[i];int R=i;
			for(auto &it : VR[i+1])
			{
				int g=__gcd(curg,it.g);
				if(g!=curg) VR[i].push_back(G(R,curg));
				curg=g; R=it.id;
			}
			VR[i].push_back(G(R,curg));
		}
	}
}

/// 计算L,R之间的值
LL calu(int type,int L,int R)
{
	LL ret=0;
	if(type==0)
	{
		int tr=R;
		for(auto &it : VL[R])
		{
			if(it.id>=L)
			{
				ret+=(tr-it.id+1)*it.g;
				tr=it.id-1;
			}
			else
			{
				ret+=(tr-L+1)*it.g;
				break;
			}
		}
	}
	else if(type==1)
	{
		int tr=L;
		for(auto &it : VR[L])
		{
			if(it.id<=R)
			{
				ret+=(it.id-tr+1)*it.g;
				tr=it.id+1;
			}
			else
			{
				ret+=(R-tr+1)*it.g;
				break;
			}
		}
	}
	return ret;
}

LL ans[maxn];

int main()
{
	int T_T;
	scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        PreInit();

		scanf("%d",&Q);
        for(int i=0,l,r;i<Q;i++)
        {
            scanf("%d%d",&l,&r);
            que[i].L=l; que[i].R=r; que[i].id=i;
        }
        sort(que,que+Q);

		int L=1,R=0; LL ret=0;
		for(int i=0;i<Q;i++)
		{
			while(R<que[i].R)
			{
				R++;
				ret+=calu(0,L,R);
			}
			while(R>que[i].R)
			{
				ret-=calu(0,L,R);
				R--;
			}
			while(L<que[i].L)
			{
				ret-=calu(1,L,R);
				L++;
			}
			while(L>que[i].L)
			{
				L--;
				ret+=calu(1,L,R);
			}
			ans[que[i].id]=ret;
		}

		for(int i=0;i<Q;i++)
			cout<<ans[i]<<endl;
    }
    return 0;
}



HDOJ 5381 The sum of gcd 莫队算法


联系
我们