#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[1000010],st[1000010][25],lg2[1000010];
ll tot[1000010];
int get(int l,int r){
	int d=lg2[r-l+1];
	return __gcd(st[l][d],st[r-(1<<d)+1][d]);
}
int gcd(int a, int b) {
	if(!a)return b;
	if(!b)return a;
	int shift=__builtin_ctz(a|b);
	a>>=__builtin_ctz(a);
	do{
		b>>=__builtin_ctz(b);
		if(a>b)swap(a,b);
	b-=a;
	}while(b);
	return a << shift;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	lg2[0]=1;
	for(int i=2;i<=1000000;i++){
		lg2[i]=lg2[i>>1]+1;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		st[i][0]=a[i];
		tot[i]=tot[i-1]+a[i];
	}
	for(int i=1;i<=20;i++){
		for(int x=1;x+(1<<i)-1<=n;x++){
			st[x][i]=gcd(st[x][i-1],st[x+(1<<i-1)][i-1]);
		}
	}
	ll ans=0;
	for(int i=k;i<=n;i++){
		int p=get(i-k+1,i),la=-1;
		while(114514){
			int l=1,r=i-k+1;
			while(l<r){
				int mid=(l+r)>>1;
				if(get(mid,i)<p)l=mid+1;
				else r=mid;
			}
			ans=max(ans,(ll)p*(tot[i]-tot[l-1]));
			if(l==1)break;
			p=gcd(p,a[l-1]);
			la=l;
		}
	}
	cout<<ans;
	return 0;
}

前言

校内模拟赛考了，于是写篇题解讲自己的做法。

题目链接。

题目大意

给出一个长度为 $n$ 的数组 $h$ 和一个限制 $k$，求

$$\max_{1\le l\le l+k-1\le r\le n}\left\{\gcd_{i=l}^{r}\{a_i\}\times\sum_{i=l}^{r}a_i\right\}\tag{1}$$

基本思路

赛时看到题目想到的是枚举 $\gcd$ 然后 dp。具体的，设 $dp(i,j)$ 表示最大化 $dp(i,j)$，使得 $h$ 中 $[i-dp(i,j)+1,i]$ 的公约数为 $j$。转移方程：

$$dp(i,j)= \begin{cases} dp(i-1,j)+1 & \text{if } j\mid a_i\\ 0 & \text{otherwise} \end{cases}\tag{2}$$

如果 $dp(i,j)\ge k$ 则更新答案：

$$ans\gets\max\left(ans,j\times \sum_{\mathclap{l=i-dp(i,j)+1}}^{i}a_i\;\right)\tag{3}$$

因为 $n,h_i\le 10^6$，直接 dp 肯定是不行的。

优化

首先要滚动数组，滚去 $i$ 这维。

其次 $(3)$ 中求和需要用前缀和优化。

还有枚举 $a_i$ 的约数 $j$ 也需要优化：对于每个数开一个 vector 存其约数，倒序枚举 $j$ 的倍数 $m$ 并将 $j$ 加入 $m$ 的 vector。这部分是调和级数 $O(V\ln V)$ 的，$V$ 表示值域。

接着注意到 $(2)$ 的 $\text{otherwise}$ 需要将 $dp(i,j)$ 置为 $0$。暴力清空肯定不行。

1. 可以使用时间戳优化：更新 $dp(j)$ 时将其时间戳（最近更新时间）$tag(j)\gets i$。转移时如果 $tag(j)=i-1$，则 $dp(j)\gets dp(j)+1$，反之 $dp(j)\gets 1$。这也是代码中的实现方式
2. 也可以直接判断是否满足 $j\mid a_{i-1}$，如果是，则 $i-1$ 时必然更新过 $dp(j)$，反之没有。

时间复杂度 $O(V\ln V+\sum d(a_i))$，$d(x)$ 表示 $x$ 的约数个数。

不懂可以看代码。

代码

还是很简洁的，压了行。

#include <iostream>
#include <vector>

using std::cin;
typedef long long ll;
constexpr int N=1e6+114514;
int n,k,V;
int a[N];
ll s[N]; // 前缀和
int dp[N],tag[N]; // dp 数组和时间戳
std::vector<int> e[N];

int gcd(int x,int y){return !y?x:gcd(y,x%y);}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>k; // 求前缀和、值域大小
	for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i],V=std::max(V,a[i]);
	// 枚举倍数求约数。e[x] 表示 x 的约数
	for(int i=1;i<=V;i++)for(int j=1;i*j<=V;j++)e[i*j].push_back(i);
	ll ans=0;
	for(int i=1;i<=n;i++)for(int j:e[a[i]])
	{
		if(tag[j]==i-1)dp[j]++; // 如果上次有更新（没清 0）则累加
		else dp[j]=1; // 反之上次会清 0，置成 1
		tag[j]=i; // 更新时间戳
		if(dp[j]>=k)ans=std::max(ans,(s[i]-s[i-dp[j]])*j); // 更新答案
	}
	printf("%lld",ans);
	return 0;
}