1. 题目

传送门＝￣ω￣＝
题目描述

给定一行 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 <= 100， m <= 10

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

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

0 < 数字大小 <= 1,000,000,000

2. 思路

数据范围:1000，直接枚举，预处理 f[i][j]。f[i][j] 指区间 [i,j] 的最大公约数，递推式为：

f[i][i]=a[i],f[i][j]=gcd(f[i][j-1],a[i]);

这应该很明显吧！Ｏ（∩＿∩）Ｏ～

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1005],f[1005][1005];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int read()
{
    int ans=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){ans=ans*10+c-'0',c=getchar();}
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),f[i][i]=a[i];
    for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)f[i][j]=gcd(f[i][j-1],a[j]);
    for(int i=1,l,r;i<=m;i++)l=read(),r=read(),printf("%d\n",f[l][r]);
    return 0;
}