考试题。
发现 \(g\) 的值是若干个相同的段，且段数很少，因为每次取 \(\gcd\) 至少会将值域变为原来的一半。所以段数是 \(\mathcal{O}(\log V)\) 的。
然后就可以从小到大枚举左端点，然后枚举 \(g\) 的值，找的是最远的满足 \(\gcd(a_l,\dots,a_r)=g\) 的 \(r\)，这里可以使用二分。二分的 check 使用 ST 表即可做到 \(\mathcal{O}(n\log n\log^2V)\)。\(k\) 的话再判断一下就行。常数极小，可以通过。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int a[1000010],gc[22][1000010];
ll s[1000010];
int gcd(int a,int b){
while(b)swap(a%=b,b);
return a;
}
int ask(int l,int r){
int d=__lg(r-l+1);
return gcd(gc[d][l],gc[d][r-(1<<d)+1]);
}
int work(int st,int lim,int g){
int l=lim,r=n,res=lim;
while(l<=r){
int mid=(l+r)>>1;
if(ask(st,mid)==g)l=mid+1,res=mid;
else r=mid-1;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),gc[0][i]=a[i],s[i]=s[i-1]+a[i];
for(int i=1;i<=__lg(n);i++)for(int j=1;j+(1<<i)-1<=n;j++)gc[i][j]=gcd(gc[i-1][j],gc[i-1][j+(1<<i-1)]);
ll ans=a[n];
for(int i=1;i<=n-m+1;i++){
int x=i+m-1;ans=max(ans,ask(i,i+m-1)*1ll*(s[i+m-1]-s[i-1]));
while(x<n){
int g=ask(i,x+1);
int p=work(i,x+1,g);
if(p-i+1>=m)ans=max(ans,(s[p]-s[i-1])*g);
x=p;
}
}
printf("%lld\n",ans);
return 0;
}
但是这个东西显然不是正解。正难则反，发现 \(i\) 的右端点容易由 \(i+1\) 得到。故可以从大到小的枚举 \(i\)。然后用一个数据结构（比如链表）存下当前 \(\log V\) 个 \(\gcd\) 的位置。将这些 \(\gcd\) 都和 \(h_i\) 做一遍即可。然后相同的取较大的即可。