说实话不知道为什么这个题在dp的题单，也没什么有决策性的地方，个人更倾向于这是个递推的题

#include<iostream>
using namespace std;
int n,m;
int a[1005],dp[1005][1005];
int gcd(int a,int b){return (!b?a:gcd(b,a%b));}
int dfs(int l,int r){
    if(l>r) return 0;
    if(l==r) return dp[l][r]=a[l];
    if(dp[l][r]) return dp[l][r];
    return dp[l][r]=gcd(a[l],dfs(l+1,r));
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<dfs(l,r)<<endl;
    }
    return 0;
}

分享dp解法：

题目数据n<=1000,m<=1e6,正常暴力肯定不行,所以可以先预处理出所有1->n之间的最大公因数。

可以用一个f[i][j]数组表示示第i个数到j个数的最大公因数

输入时自己到自己的最大公因数=自己，所以为

  cin>>f[i][i];

主题部分：

//用样例n=5,m=3,[a1,a2...an]=[4,12,3,6,7]做演示 
//i=4,j=5时： 
		//a[4]和a[5]的最大公因=gcdx(6,7)=f[4][5]=1;
//i=3,j=4时：
		//a[3]到a[4]的最大公因=gcdx(3,6)=f[3][4]=3;
//i=3,j=5时：
		//a[3]到a[5]的最大公因=gcdx(3,1)=f[3][5]=1;
//.....以此类推 
for(int i=n-1;i>=1;i--){//枚举启示点
		for(int j=i+1;j<=n;j++){//枚举到达点
			f[i][j]=gcdx(f[i][i],f[i+1][j]);
		}
	}

最后查询f[l][r]即可

#include<iostream>
using namespace std;
int n,m,a[1010],dp[1010][1010],lll,rrr;
int gcd(int a,int b){
  //辗转相除法
	if(b==0)return a;
	return gcd(b,a%b);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][i]=a[i]; 
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			dp[i][j]=gcd(dp[i][j-1],a[j]);//m到了1e6，就不能直接写了，要预处理
            //容易想到就是这个数和前一个dp数组的最大公因数
		}
	}
	while(m--){
	    cin>>lll>>rrr;
	    cout<<dp[lll][rrr]<<endl;
	}    
	return 0;
}