gcd区间 (ST表)(爱思创算法四)

前言:

本题为作业

题目描述

给定一行n个正整数a[1]..a[n]。

m次询问，

每次询问给定一个区间[L,R]，

输出a[L]..a[R]的最大公因数。

输入格式

第一行两个整数n，m。

第二行n个整数表示a[1]..a[n]。

以下m行，

每行2个整数表示询问区间的左右端点。

保证输入数据合法。

输出格式

共m行，每行表示一个询问的答案。

样例输入

5 3
4 12 3 6 7
1 3
2 3
5 5

样例输出

1
3
7

问题提示

对于30%的数据，n <= 100， m <= 10

对于60%的数据，m <= 1000

对于100%的数据，1 <= n <= 1000，1 <= m <= 1,000,000

解题思路

我们看题目是寻找 a[L]~a[R] 这片区间之内的一个最大公因数，

可以用ST表多次求解连续区域的最大公因数。

AC完整代码:

#include
using namespace std;
const int N=1e3+5;
int n,m,a[N],f[N][N];
int gcd(int x,int y)//最大公约数函数
{
	int i,j;
	while(y)
	{
		int r=x%y;//辗转相除法
		x=y;
		y=r;
	}
	return x;
}
int main()
{
	int i,j,l,r;//套用ST表模板
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i][i]=a[i];
	}
	for(i=1;i
	{
		for(j=i+1;j<=n;j++)
		{
			f[i][j]=gcd(f[i][j-1],a[j]);
		}
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",f[l][r]);
	}
	return 0;
}

AC