自动搬运

查看原文

来自洛谷，原作者为

	C3H5ClO 金发吸血鬼赛高！

搬运于2025-08-24 22:28:01，当前版本为作者最后更新于2021-01-09 16:10:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

学考回来随便开了一个比赛，提供一个 $O(n\sigma_0(a_i))$ 的分治做法。

显然，答案必然是全局最大值的约数。那么我们枚举这个约数 $x$ 。对每个 $x$ ，求出将这个序列划分成若干段，每一段的最大值都是 $x$ 的倍数，段数的最大值。满足这个段数 $\ge k$ 的最大的 $x$ 就是答案。

对于一个区间 $l,r$，考虑求出它能划分的最多段数 $f(l,r)$ 。设区间最大值所在位置是 $mid$ 。

如果 $x|a_{mid}$ ，那么贪心地取这个最大值为新的一段， $f(l,r)=f(l,mid-1)+1+f(mid+1,r)$ 。

否则，如果 $l>1$，$l-1$ 这个位置一定是某一个祖先的 $mid$ ， $[l,r]$ 的最大值可以属于 $l-1$ 所在区间。同理，如果 $r<n$，$[l,r]$ 的最大值可以属于 $r+1$ 所在区间。因此， $f(l,r)=max([r<n]f(l,mid-1),[l>1]f(mid+1,r))$ 。

显然，递归树是笛卡尔树的一部分，求一次 $f(l,r)$ 的复杂度为 $O(n)$ ，因此时间复杂度得证。

至于区间最大值位置的求法，可以建笛卡尔树也可以直接ST表。

代码有手就行

const int N=100005;
int n,k,a[N],st[N][20],lg[N];
inline int pushup(int x,int y){return a[x]>a[y]?x:y;}
inline int getmax(int l,int r)
{
	int d=lg[r-l+1];
	return pushup(st[l][d],st[r-(1<<d)+1][d]);
}
int solve(int l,int r,int d)
{
	if(l>r)return 0;
	int mid=getmax(l,r);
	if(a[mid]%d==0)return solve(l,mid-1,d)+1+solve(mid+1,r,d);
	int ans=0;
	if(l>1)chkmax(ans,solve(mid+1,r,d));
	if(r<n)chkmax(ans,solve(l,mid-1,d));
	return ans;
}
int main()
{
	scanf("%d%d",&n,&k);
	For(i,2,n)lg[i]=lg[i>>1]+1;
	For(i,1,n)scanf("%d",a+i),st[i][0]=i;
	For(i,1,lg[n])
		For(j,1,n-(1<<i)+1)
			st[j][i]=pushup(st[j][i-1],st[j+(1<<i-1)][i-1]);
	int x=a[getmax(1,n)],sqx=sqrt(x);
	For(i,1,sqx)
		if(x%i==0&&solve(1,n,x/i)>=k)
		{
			printf("%d",x/i);
			return 0;
		}
	Rof(i,sqx-1,1)
		if(x%i==0&&solve(1,n,i)>=k)
		{
			printf("%d",i);
			return 0;
		}
}