题意
给定 \(a\) 序列，一个区间的权值为区间 \(\gcd\) 乘上区间和，求长度 \(\ge k\) 的区间的最大权值。
\(1\le n,V\le 10^6\)
题解
区间 \(\gcd\) 相较于区间和更难维护，考虑枚举 \(\gcd\)。
记当前钦定的 \(\gcd\) 为 \(x\)，那么我们选择的区间一定是极长的包含 \(x\) 倍数的连续段，否则从长度限制上和区间和上都会更劣。
直接枚举所有 \(x\) 然后 \(O(n)\) 扫一遍的 \(O(nV)\) 复杂度是不能接受的，但是考虑到此处 \(V\le 10^6\)，意味着 \(d(a_i)\le 240\)，这里 \(d\) 为正因数个数。
所以我们维护每个 \(x\) 当前的连续段区间，扫一遍所有 \(a_i\) 并枚举 \(a_i\) 的所有因数 \(d\)，然后判断 \(d\) 是否在这里产生了新的连续段，如果是就计算上个连续段的答案并记录新的连续段，否则更新连续段右端点为 \(i\) 即可。
时间复杂度为 \(O(\sum d(a_i))\)，最坏情况下达到 \(O(240n)\)，大概要跑 \(1.5s\)。
\(\texttt{Code}\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
char buf[1<<22],*p1=buf,*p2=buf;
const int N=1e6+10;
int n,k,a[N],mx;
ll s[N],ans;
#define pb emplace_back
vector<int>d[N];
#define pii pair<int,int>
#define mkp make_pair
pii pos[N];
il int read(){
re int x=0;re char c=getchar(),f=0;
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f?-x:x;
}
#define l(x) pos[x].first
#define r(x) pos[x].second
int main(){
// freopen("intelligence.in","r",stdin);
// freopen("intelligence.out","w",stdout);
n=read(),k=read();
for(re int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),s[i]=s[i-1]+a[i];
const int V=mx;
for(re int i=1;i*i<=V;i++){
d[i*i].pb(i);
for(re int j=i+1;j*i<=V;j++)d[i*j].pb(i),d[i*j].pb(j);
}
for(re int i=1;i<=V;i++)r(i)=-1;
for(int x:d[a[1]])pos[x]=mkp(1,1);
for(re int i=2;i<=n;i++)
for(int x:d[a[i]]){
if(r(x)==i-1)r(x)=i;
else{
if(r(x)-l(x)+1>=k)ans=max(ans,x*(s[r(x)]-s[l(x)-1]));
pos[x]=mkp(i,i);
}
}
for(re int i=1;i<=V;i++)
if(r(i)-l(i)+1>=k)ans=max(ans,i*(s[r(i)]-s[l(i)-1]));
cout<<ans;
return 0;
}