题目描述

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

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

输入输出格式

输入格式：

第一行两个整数n，m。

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

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

保证输入数据合法。

输出格式：

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

输入输出样例

输入样例#1：

5 34 12 3 6 71 32 35 5

输出样例#1：

137

说明

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

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

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

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

---

 

序列固定、区间查询===>离线处理===>考虑st表！

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int maxn=2001; 7 int n,m; 8 int stgcd[maxn][20],mn[maxn]; 9 int a[maxn];10 11 int gcd(int a,int b){  return b==0?a:gcd(b,a%b);  }12 13 void init(){14     mn[0]=-1;15     for(int i=1;i<=n;i++){16         mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];17         stgcd[i][0]=a[i];18     }19     for(int j=1;j<=mn[n];j++)20         for(int i=1;i+(1<
        
         <=n;i++){21             stgcd[i][j]=gcd(stgcd[i][j-1],stgcd[i+(1<<(j-1))][j-1]);22         }23 }24 25 int rmq_gcd(int left,int right){26     int k=mn[right-left+1];27     return gcd(stgcd[left][k],stgcd[right-(1<