注意到对于任意元素，以他为左端点的区间的不同的 gcd 不超过 $40$ 个。且单调递减。

所以直接 st 表预处理加上二分每一个会出现的 gcd 的最远位置即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int st[N][20],a[N];
int get(int l,int r)
{
	int k=log2(r-l+1);
	return __gcd(st[l][k],st[r-(1<<k)+1][k]);
}
signed main()
{
	int n;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 i=1;i<=19;i++)for(int j=1;j+(1<<i)-1<=n;j++)
		st[j][i]=__gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(j<=n)
		{
			int p=get(i,j);
			int l=j,r=n,res=j;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(get(i,mid)==p)l=mid+1,res=mid;
				else r=mid-1;
			}
			ans=max(ans,p*(res-i+1));
			j=res+1;
		}
	}
	cout<<ans;
	return 0;
}

前言：感觉题解区的方法有些困难，于是写了一篇题解。

题意：

求 $W(L,R) = (R-L+1) × \gcd (A_l,...,A_r)$ 的最大值。

思路

子序列问题通常可以使用分治算法来解决，我们考虑怎样算左右区间中间的值，发现 $\gcd$ 的个数不超过 $\log V$ 于是可以暴力找出所有的的 $\gcd$ 处在的离中间最远的位置，暴力计算每一对即可。

#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int MAXN=2e5+10;
int n,a[MAXN],res,c[MAXN];
void solve(int l,int r){
	if(l==r) return res=max(res,a[l]),void();
	int mid=l+r>>1;
	solve(l,mid);solve(mid+1,r);
	int now=a[mid+1];unordered_map<int,int>mpr,mpl;mpr[now]=mid+1;
	for(int i=mid+2;i<=r;i++) {
		now=__gcd(now,a[i]),mpr[now]=i;
	}now=a[mid];mpl[now]=mid;
	for(int i=mid-1;i>=l;i--) now=__gcd(now,a[i]),mpl[now]=i;
	for(auto x:mpl){
		for(auto y:mpr){
			res=max(res,__gcd(x.fi,y.fi)*(y.se-x.se+1));
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	solve(1,n);cout<<res;
	return 0;
}