题目描述

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

m次询问,每次询问给定一个区间[L,R],输出a[L]…a[R]的最大公因数。

输入格式

第一行两个整数n,m。

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

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

保证输入数据合法。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

1
3
7

说明/提示

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

对于60%的数据,m<=103m <= 10^3

对于100%的数据,1<=n<=1031<=m<=106,0<数字大小<=1091 <= n <= 10^3,1 <= m <= 10^6, 0 < 数字大小 <= 10^9

题目分析

最大公约数的一个特点就是 gcd(a,b,c)=gcd(gcd(a,b),gcd(b,c))gcd(a,b,c)=gcd(gcd(a,b),gcd(b,c))

那么gcd(alar)=gcd(gcd(alamid),gcd(amid+1,ar))gcd(a_l\sim a_r)=gcd(gcd(a_l\sim a_{mid}),gcd(a_{mid+1},a_r))

利用ST表,由区间最值修改为区间gcd的寻找。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e3+5;
int n,m;
int gcd(int a,int b){//辗转相除法求最大公约数
	while(b){
		int r=a%b;
		a=b;
		b=r;
	}
	return a;
}
int a[N];
int Log[N];//Log[x]=log2(x)
int st[N][N];//st[i][j]=gcd(i ~ i+(1<<j)-1) 
int main(){
	int n,m,l,r;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	//预处理 Log[] 数组
	Log[1]=0,Log[2]=1;
	for(int i=3;i<=n;i++){
		Log[i]=Log[i/2]+1;
	}
	
	//单个元素的最大公约数是自己
	for(int i=1;i<=n;i++){
		st[i][0]=a[i];
	}
	//预处理 ST表
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+((1<<j)-1)<=n;i++){
			st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		scanf("%d%d",&l,&r);
		int len=r-l+1;
		int Lg=Log[len];
		//求区间内的最大公约数
		printf("%d\n",gcd(st[l][Lg],st[r-(1<<Lg)+1][Lg]));
	}
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)