这题和P7009一模一样，可是我同样的代码在这里超时了，而P7009的代码只跑了2.43s，求条。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=105;
int n,m,a[N],LOG[N],st[N][M],ans; 
int ggcd(int x,int y){
    int c=x%y;
    while(y!=0){c=x%y;x=y;y=c;}
    return x;
}
int st_q(int l,int r){
    int k=LOG[r-l+1];
    int gcd=ggcd(st[l][k],st[r-(1<<k)+1][k]);
    return gcd;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)st[i][0]=a[i];
    for(int k=1;k<=LOG[n];k++){
        int len=1<<k;
        for(int i=1;i<=n-len+1;i++){
            st[i][k]=ggcd(st[i][k-1],st[i+(1<<k-1)][k-1]);
        }
    }
    ans=0;
    for(int i=1;i<=n;i++){
        int x=i;
        while(x<=n){
            int l=x,r=n+1,mid;
            while(l+1<r){
                mid=(l+r)/2;
                if(st_q(i,mid)==st_q(i,x))l=mid;
                else r=mid;
            }
            ans=max(ans,st_q(i,x)*(l-i+1));
            x=l+1;
        }
    }
    cout<<ans<<endl;
    return;
}
signed main(){
    LOG[0]=-1;
    for(int i=1;i<=N;i++)LOG[i]=LOG[i>>1]+1;
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

复杂度应该是 $O(tn\log n)$ 的。