OI——GCD(HDU5726)

封面女神:Rihanna,8座格莱美的在美国发展的巴巴多斯籍歌手,代表作《Diamonds》

帅气的高俊峰学长讲ST表的时候,讲了一道GCD的题。题面如下:

然而没什么可以复制上来的,因为垃圾HDU写的很苟。

其实核心就是gcd的左端点固定,右端点递增,gcd的值不会增大。

代码如下

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
map<int,long long> mp;
int n;
int f[200000][32],a[200000];
int gcd(int a,int b)
{
	return b == 0?a:gcd(b,a%b);
}
void fore()
{
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
	}
	int Log=(int)log2(double(n));
	for(int j=1;j<=Log;j++){
		for(int i=1;i <= n && i+(1 << j)-1 <= n;i++)
		{
			f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	return;
}
int query(int x,int y)
{
	if (x>y) swap(x,y);
	int Log=(int)log2(double(y-x+1));
	return gcd(f[x][Log],f[y-(1<<Log)+1][Log]);
}
void fk()
{
	mp.clear();
	for(int i=1;i<=n;i++)
	{
		int g=f[i][0],j=i;
		while(j<=n)
		{
			int l=j,r=n;
			while(l<r)
			{
				int mid=(l+r+1)/2;
				if (query(i,mid)==g) l=mid;
				else r=mid-1;
			}
			mp[g]+=r-j+1;
			j=l+1;
			g=query(i,j);
		}
	}
	return;
}
int main()
{
	int T;
	scanf("%d",&T);
	int cas=1;
	while(T--)
	{
		printf("Case #%d:\n",cas++);
		memset(f,0,sizeof(f));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		fore();
		fk();
		int q;
		scanf("%d",&q);
		while(q--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			int g=query(x,y);
			printf("%d %lld\n",g,mp[g]);
		}
	}
	return 0;
}

求打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注