GCD HDU - 5726 线段树+数学

60 阅读 0 评论 40 点赞

我是靠谱客的博主奋斗冰棍，最近开发中收集的这篇文章主要介绍GCD HDU - 5726 线段树+数学，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Give you a sequence of N(N≤100,000)N(N≤100,000) integers : a1,...,an(0<ai≤1000,000,000)a1,...,an(0<ai≤1000,000,000). There are Q(Q≤100,000)Q(Q≤100,000) queries. For each query l,rl,r you have to calculate gcd(al,,al+1,...,ar)gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤l<r≤N)(l′,r′)(1≤l<r≤N)such that gcd(al′,al′+1,...,ar′)gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar)gcd(al,al+1,...,ar).

Input

The first line of input contains a number TT, which stands for the number of test cases you need to solve.

The first line of each case contains a number NN, denoting the number of integers.

The second line contains NN integers, a1,...,an(0<ai≤1000,000,000)a1,...,an(0<ai≤1000,000,000).

The third line contains a number QQ, denoting the number of queries.

For the next QQ lines, i-th line contains two number , stand for the li,rili,ri, stand for the i-th queries.

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes, ttmeans the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar)gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′)(l′,r′) such that gcd(al′,al′+1,...,ar′)gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar)gcd(al,al+1,...,ar).

Sample Input

Sample Output

Case #1:
1 8
2 4
2 4
6 1

题意：T组样例，给定一个长度为n的序列，给你m个询问，每个询问给你一个区间[L,R],让你求[L,R]的gcd以及在所有区间里与[L,R]的gcd相同的区间的个数。

思路：求[L,R]区间的gcd好求，但是求在所有区间中有多少区间和其gcd相同好像没那么容易。我们最容易想到的方法是暴力，暴力可行吗？我们都知道GCD是有单调性的，并且GCD是连续的。以4开头往后区间的gcd可能为：4 4 2 2 2 2 1 1 1 1 而不可能为：4 2 2 1 1 1 2 2 1 4 。对于一个数n，任何数与他构成gcd的个数不会超过logn个，因为一个数的质因子不会超过logn个。这给我们暴力一个想法：固定区间的左端点，暴力查询以它为开头的区间有多少种GCD，查询速度大约是O(nlogn)。

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
map<ll,ll> mp;
int a[maxn],n;
struct node{
	int l;
	int r;
	int sum;
}tree[maxn<<2];
void pushup(int cur)
{
	tree[cur].sum=__gcd(tree[cur<<1].sum,tree[cur<<1|1].sum);
}
void build(int l,int r,int cur)
{
	tree[cur].l=l;
	tree[cur].r=r;
	if(l==r) 
	{
		tree[cur].sum=a[l];
		return ;
	}
	int m=(l+r)>>1;
	build(l,m,cur<<1);
	build(m+1,r,cur<<1|1);
	pushup(cur);
}
int query1(int L,int R,int val,int cur)
{
	if(L<=tree[cur].l&&tree[cur].r<=R&&tree[cur].sum%val==0) return 0;
	if(tree[cur].l==tree[cur].r) return tree[cur].l;
	int res=0;
	if(L<=tree[cur<<1].r) res=query1(L,R,val,cur<<1);
	if(R>tree[cur<<1].r&&res==0) res=query1(L,R,val,cur<<1|1);
	return res;
}
int query2(int L,int R,int cur)
{
	if(L<=tree[cur].l&&tree[cur].r<=R) return tree[cur].sum;
	int res=0;
	if(L<=tree[cur<<1].r) res=__gcd(res,query2(L,R,cur<<1));
	if(R>tree[cur<<1].r) res=__gcd(res,query2(L,R,cur<<1|1));
	return res;
}
void init()
{
	int tmp,tgcd,jmp;
	for(int i=1;i<=n;i++)
	{
		tmp=i,tgcd=a[i];
		while(tmp<=n)
		{
			jmp=query1(tmp,n,tgcd,1);
			if(jmp==0) jmp=n+1;
			mp[tgcd]+=jmp-tmp;
			tgcd=__gcd(a[jmp],tgcd);
			tmp=jmp;
		}
	}
}
int main()
{
	int t,q,l,r,ans1;
	ll ans2;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++)
	{
		mp.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		build(1,n,1);
		init();
		scanf("%d",&q);
		printf("Case #%d:n",cas);
		while(q--)
		{
			scanf("%d%d",&l,&r);
			ans1=query2(l,r,1);
			ans2=mp[ans1];
			printf("%d %lldn",ans1,ans2);
		}
	}
	return 0;
}