P9032 [COCI2022-2023#1] Neboderi 题解

P9032

考试题。

发现 \(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\) 做一遍即可。然后相同的取较大的即可。