问T4MLE了如何优化？

[徐沣]

#include <bits/stdc++.h>
using namespace std;
int a[20010],dp[20010][20010],n,m,l,r;
int gcd(int a,int b){
    if(b==0)
        return a;
    gcd(b,a%b);
}
void work(int n){
    for(int i=1;i<=n;i++) 
        dp[i][0]=a[i];
    for (int j=1;(1<<j)<=n;j++) 
        for(int i=1;i+(1<<j)-1<=n;i++) 
            dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int l, int r) {
    int k=0;
    while((1<<(k+1))<=r-l+1)
        k++;
    return gcd(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    work(n);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",RMQ(l,r));
    }
}

[段炜杭]

这很好笑

[段炜杭]

你算算10000*10000大不大于1e8

[徐沣]

那是不是要改成以为ST表

[段炜杭]

哥们，你过T2了吗，你看看T2你咋写的

[王建力]

是的，st 不需要开这么大