对序列A, 求 (j-i+1) * gcd( i, i+1, ... j ) 最大值
G(i) =gcd( G[i-1] ,a[i] ) 即前缀值不升
维护 1~j-1 可能的 i 值 （logn 个)
O（n *log^2
#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std ;
const int N =1e5+30;
#define int long long
int n,a[N];
int v[100],id[100],tot ;
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int max(int x,int y){
return x>y?x:y;
}
void sov(){
tot=0;
int i,j,k,ans=0;
cin>>n;
for(i=1;i<=n;++i) cin>>a[i];
for(i=1;i<=n;++i){
ans=max(ans,a[i]);
for(j=1;j<=tot;j++){
v[j]=gcd(v[j],a[i]);
if(v[j]==v[j-1]){
for(k=j;k<tot;k++){
v[k]=v[k+1],id[k]=id[k+1];
}
tot--,j--;
}
else
ans=max(ans,v[j]*(i-id[j]+1));
}
v[++tot]=a[i]; id[tot]=i;
}
cout << ans<<endl;
}
signed main(){
int tes;
cin>>tes;
while(tes--) sov();
}