Hdu-5726 GCD (二分 + RMQ)

62 阅读 0 评论 41 点赞

我是靠谱客的博主鲤鱼衬衫，最近开发中收集的这篇文章主要介绍Hdu-5726 GCD (二分 + RMQ)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

Give you a sequence of

N(N≤100,000) integers :

a1,...,an(0<ai≤1000,000,000) . There are

Q(Q≤100,000) queries. For each query

l,r you have to calculate

gcd(al,,al+1,...,ar) and count the number of pairs

(l′,r′)(1≤l<r≤N) such that

gcd(al′,al′+1,...,ar′) equal

gcd(al,al+1,...,ar) .

Input

The first line of input contains a number

T , which stands for the number of test cases you need to solve.

The first line of each case contains a number

N , denoting the number of integers.

The second line contains

N integers,

a1,...,an(0<ai≤1000,000,000) .

The third line contains a number

Q , denoting the number of queries.

For the next

Q lines, i-th line contains two number , stand for the

li,ri , stand for the i-th queries.

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes,

t means 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) and the second number stands for the number of pairs

(l′,r′) such that

gcd(al′,al′+1,...,ar′) equal

gcd(al,al+1,...,ar) .

Sample Input

Sample Output

Author

HIT

Source

2016 Multi-University Training Contest 1

Recommend

wange2014 | We have carefully selected several similar problems for you: 5733 5732 5731 5730 5729

题意：给你一个序列，有一些询问，每次问你一个区间的所有数的GCD是多少，还有这个GCD在整个区间出现的次数是多少。

分析：RMQ可以很容易的解决区间GCD的询问，关键是求出这个值在整个区间出现的次数，注意到1000000000的因数的个数是log级别的，所以我们可以枚举区间左端点来二分右端点，这样预处理出每个GCD出现的次数。

#include <map>
#include <cmath>
#include <cstdio>
#include <stdlib.h> 
#include <fstream> 
#include <utility>
#include <time.h> 
#include <algorithm> 
#include <iostream>
#define got(i) (1 << i) 
using namespace std;
int T,n,tot,q,a[100007],f[100007][20];
map <int,long long> F;
long long gcd(long long a,long long b)
{
	if(a % b == 0) return b;
	return gcd(b,a % b);
}
long long qugcd(int l,int r)
{
	int leng = log2(r-l+1);
	return gcd(f[l][leng],f[r-got(leng)+1][leng]);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		F.clear();
		scanf("%d",&n);
		for(int i = 1;i <= n;i++) 
		{
			scanf("%d",&a[i]);
			f[i][0] = a[i];
		}
		for(int i = 1;got(i) <= n;i++)
		 for(int j = 1;j + got(i) - 1 <= n;j++)
		  f[j][i] = gcd(f[j][i-1],f[j+got(i-1)][i-1]);
		for(int i = 1;i <= n;i++)
		{
			int s = i;
			long long now = a[i];
			while(s != n+1)
			{
				int t = n,pre = s;
				while(s != t)
				{
					int mid = (s + t)/2 + 1;
					if(qugcd(s,mid) == now) s = mid;
					else t = mid-1; 
				}
				F[now] += t - pre + 1ll;
				s++;
				if(s != n+1) now = gcd(now,a[s]); 
			}
		}
		printf("Case #%d:n",++tot);
		scanf("%d",&q);
		for(int i = 1;i <= q;i++)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			long long ans = qugcd(l,r);
			printf("%I64d %I64dn",ans,F[ans]);
		}
	}
 }