【题解】gcd区间（ST表）

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

1
3
7

#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;
}