COCI2022-2023#1 Neboderi

P9032 [COCI2022-2023#1] Neboderi

题目大意

有一个长度为$n$的序列$h_i$，你需要从中选择一个长度大于等于$k$的子区间$[l,r]$，使得$g\times (h_l+h_{l+1}+\cdots +h_r)$最小，其中$g=\gcd (h_l,h_{l+1},\dots ,h_r)$。

$1\le k\le n\le 10^6,1\le h_i\le 10^6$

题解

当确定了$l$时，$\gcd (h_l,h_{l+1},\dots ,h_r)$随着$r$的增大而减小。

每当$\gcd$减小时，其$\gcd$相对于原来的$\gcd$肯定有若干个质因数的次数减小。那么，对于一个确定的$l$，$\gcd (h_l,h_{l+1},\dots ,h_r)$的取值不会超过$\log a_l$个数。

先用$ST$表维护区间$\gcd$。枚举$l$，在二分每一段$gcd$值相等的区间并取该区间的右端点作为$r$来更新答案。

设$v$为$a_i$的最大值，则时间复杂度为$O(n\log n\log v)$。

当然，这是跑不满的，而且时限为$2.50s$，所以可以过。

code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000000;
int n,k,now,v[N+5],lg[N+5],f[N+5][20];
long long ans=0,sum[N+5];
int gcd(int i,int j){while(j){i%=j;swap(i,j);}return i;
}
int gt(int l,int r){int x=lg[r-l+1];return gcd(f[l][x],f[r-(1<<x)+1][x]);
}
int to(int w,int be,int hv){int l=be+1,r=n,mid;while(l<=r){mid=l+r>>1;if(gt(w,mid)>=hv) l=mid+1;else r=mid-1;}return l-1;
}
int main()
{scanf("%d%d",&n,&k);lg[0]=-1;for(int i=1;i<=n;i++){lg[i]=lg[i/2]+1;scanf("%d",&v[i]);sum[i]=sum[i-1]+v[i];f[i][0]=v[i];}for(int i=1;i<=19;i++){for(int j=1;j<=n-(1<<i-1);j++){f[j][i]=gcd(f[j][i-1],f[j+(1<<i-1)][i-1]);}}for(int l=1,r;l<=n-k+1;l++){now=gt(l,l+k-1);r=to(l,l+k-1,now);while(r<=n){ans=max(ans,gt(l,r)*(sum[r]-sum[l-1]));if(r==n) break;now=gt(l,r+1);r=to(l,r+1,now);}}printf("%lld",ans);return 0;
}