HDOJ 5726 GCD 二分+ST表

HDOJ 5726

题意：给定区间【L，R】求出区间【L，R】内数组中的数的GCD，并且找出所有的数对L0，R0，1<=L0<R0<=n，使得区间【L0，R0】内的GCD等于前一个GCD值

看到这个题，跟codeforces 689 D似曾相识啊！所以把两个题都一起补了

题解统一写在这儿吧

首先说做法：

ST表：用O（nlogn）的离线处理好任意区间的内的GCD值，然后做到O（1）的查询

ST表的搞法是典型的二分想法

拿最小值举例，我们要求某一段区间的最小值

可以把区间二分，先求左边区间的最小值，右边区间的最小值

那么整段区间的最小值就是上述两个值的较小值

因为GCD，MAX，MIN，LCM等都有这个性质，那么我们都可以用ST表来这样进行处理

然后呢，枚举左端点，用二分找到右端点，然后判断GCD值是否相等

然后把值统计到GCD的hash之中

为什么可以这么样做？！

因为：GCD，MAX，MIN，LCM等都是不增函数

也就是说，我们可以利用这个性质，使用ST表和二分来避免时间和空间上浪费

这个题呢，因为g值并不多，所以可以提前都给预处理好，建立一个mp的映射

codeforces 689D呢

因为不好预处理，所以涉及到两次二分的问题

第一次二分，找到右端点的左值（如果有的话）

如果有，那么进行第二次二分，找到右端点的右值，那么对应该左端点，答案的增长是右端点的区间长度

如果没有，那么说明对应该左端点，没有符合条件的右端点

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+50; 
int a[maxn][20],T,n,m;
map<int,long long> mp;

int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}

void init(){
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			a[i][j]=gcd(a[i][j-1],a[i+(1<<(j-1))][j-1]);
}

int GETGCD(int L,int R){
	int K=(int)log2((double)(1.0*(R-L+1)));
	return gcd(a[L][K],a[R-(1<<K)+1][K]);
}

void getans(){
	mp.clear();
	int l,r,g,i,j,mid;
	for(i=1;i<=n;i++){
		g=a[i][0];
		j=i;
		while(j<=n){
			l=j,r=n;
			while(l<r){
				mid=(l+r+1)>>1;
				if (GETGCD(i,mid)==g) l=mid;
				else r=mid-1;
			}
			mp[g]+=(l-j+1);
			j=l+1;
			g=GETGCD(i,j);
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d",&T);
	for(int Case=1;Case<=T;Case++){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i][0]);
		init();
		getans();
		printf("Case #%d:\n",Case);
		scanf("%d",&m);
		int l,r,g;
		while(m--){
			scanf("%d%d",&l,&r);
			g=GETGCD(l,r);
			printf("%d %I64d\n",g,mp[g]);
		}
	}
	return 0;
}