5. gcd区间问题
题目ID：20632必做题100分
最新提交：
Runtime Error
0 分
历史最高：
Runtime Error
30 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
给定 nn 个正整数 a1,a2,…,ana1,a2,…,an。
mm 次询问，每次询问给定一个区间 [l,r][l,r]，输出 al,al+1,…,aral,al+1,…,ar 的最大公因数。输入格式
第一行两个整数 n,mn,m。
第二行 nn 个整数表示 a1,a2,…,ana1,a2,…,an。
以下 mm 行，每行两个整数 l,rl,r 表示询问区间的左右端点。输出格式
共 mm 行，每行表示一个询问的答案。
样例
Input 1
5 3 4 12 3 6 7 1 3 2 3 5 5
Output 1
1 3 7
数据范围
● 对于 30%30% 的数据，1≤n≤1001≤n≤100，1≤m≤101≤m≤10；
● 对于 100%100% 的数据，1≤l≤r≤n≤200001≤l≤r≤n≤20000，1≤m≤1061≤m≤106，1≤ai≤1091≤ai≤109
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[1005];
int dp[1005][1005];
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
dp[i][i]=a[i];
}
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
dp[i][j]=__gcd(dp[i][i],dp[i+1][j]);
}
}
while(m--){
int l,r;
scanf("%lld%lld",&l,&r);
cout<<dp[l][r]<<endl;
}
return 0;
}
/*
颠倒空格
*/