hdu5726 GCD(gcd +二分+rmq)

53 阅读 0 评论 35 点赞

我是靠谱客的博主潇洒便当，最近开发中收集的这篇文章主要介绍hdu5726 GCD(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


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


题意：给你n个数，m个询问，每一个询问都是一个区间，让你先计算出这段区间所有数的gcd，然后问1~n所有连续区间中gcd的值等于询问区间gcd的区间个数。
思路：考虑到如果固定区间左端点L，那么右端点从L+1变化到n的过程中gcd最多变化log(区间内最大的数的大小)次（因为每次变化至少除以2）,那么我们就可以枚举左端点，然后每次二分值连续的区间，然后都存到map里就行了。



#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<algorithm>
using namespace std;
#define lson th<<1
#define rson th<<1|1
typedef long long ll;
typedef long double ldb;
#define inf 99999999
#define pi acos(-1.0)
#define Key_value ch[ch[root][1]][0]
map<int,ll>mp;
map<int,ll>::iterator it;
int q[100100][2];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int gcd1[100100][30];
int a[100006];
void init_rmq(int n)
{
int i,j;
for(i=1;i<=n;i++){
gcd1[i][0]=a[i];
}
for(j=1;j<=20;j++){
for(i=1;i<=n;i++){
if(i+(1<<j)-1<=n){
gcd1[i][j]=gcd(gcd1[i][j-1],gcd1[i+(1<<(j-1))][j-1]);
gcd1[i][j]=gcd(gcd1[i][j-1],gcd1[i+(1<<(j-1))][j-1]);
}
}
}
}
int getgcd(int l,int r)
{
int k,i;
if(l>r)swap(l,r);
k=(log((r-l+1)*1.0)/log(2.0));
return gcd(gcd1[l][k],gcd1[r-(1<<k)+1][k]);
}
int main()
{
int n,m,i,j,T,cas=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
mp.clear();
init_rmq(n);
int l,r,mid;
for(i=1;i<=n;i++){
//printf("----->%dn",i);
int val=a[i];
int pos=i;
while(pos<=n){
val=getgcd(i,pos);
l=pos,r=n;
while(l<=r){
mid=(l+r)/2;
if(getgcd(i,mid)==val)l=mid+1;
else r=mid-1;
}
mp[val]+=(r-pos+1);
pos=l;
}
}
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d",&q[i][0],&q[i][1]);
}
printf("Case #%d:n",++cas);
for(i=1;i<=m;i++){
printf("%d %lldn",getgcd(q[i][0],q[i][1]),mp[getgcd(q[i][0] ,q[i][1] ) ] );
}
}
return 0;
}