自动搬运

查看原文

来自洛谷，原作者为

	ytb2024 我是 闪避 ^_^

搬运于2025-08-24 21:59:54，当前版本为作者最后更新于2022-12-06 22:12:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题意：从头到尾选数，相邻两个数的 $\gcd$ 应大于等于 $L$，最多能选多少个数。

30 pts

相信很多同学的第一想法是 DP。一维 $f_i$ 表示选当前的这个数的最大值，可以 $O\left(n^2\right)$ 实现。具体为（不会写公式的蒟蒻 qwq），$j<i$ 且 $\gcd\left(a_i,a_j\right)\ge$ $L$ 时，$f_i=f_j+1$，$f_i$ 取最大值。最后 $ans$ 为所有 $f_i$ 中的最大值。

下面是代码实现，就不加注释了。（看一看前面的就知道）

#include<bits/stdc++.h>
using namespace std;
int n,l,a[50001],f[50001],ans=1;
inline void init()
{
	cin>>n>>l;
	for(int i=1;i<=n;i++)cin>>a[i],f[i]=1;
}
inline void solve()
{
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)if(__gcd(a[i],a[j])>=l)f[i]=max(f[i],f[j]+1);
		ans=max(ans,f[i]);
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	init(),solve();
	return 0;
}

100 pts

我们可以发现，题目中的 $L$ 与 $a_i$ 不超过 $10^6$。

而对 $\gcd\left(a_i,a_j\right)\ge{L}$ 的理解可以转化成 $a_i$ 与 $a_j$ 的相同约数至少要为 $L$。

由于 $L$ 与 $a_i$ 很小，所以考虑预处理所有 $a_i$ 的约数，但是小于 $L$ 的可以不管(后面会提到)。

注意：由于此题空间很小，如果数组的第二维开得太大了，就会MLE。这里经过计算后，$10^6$ 内约数最多（不包含 $1$）的是 $720720$，有约数 $239$ 个，所以考虑第二维开 $250$。

for(int i=1;i<=n;i++)
{
	int x;
	cin>>x;
	for(int j=1;j*j<=x;j++)if(x%j==0)
	{
		if(j>=l)a[i][++t[i]]=j;
		if(x/j>=l&&j*j!=x)a[i][++t[i]]=x/j;
	}
}

可以发现这相当于一个一个的组，在同一个组的数是可以用前面的更新后面的，而小于 $L$ 的明显是不可以更新值的，而上面的预处理便是把它的每一个组记录下来。

可以对每一个组开一个数组，表示这个组中目前的最大值。对于每个数，从它所在的所有组中选最大值，$+1$ 后将它在的组全部更新为这个数。

for(int i=1;i<=n;i++)
{
	int sum=0;
	for(int j=1;j<=t[i];j++)sum=max(sum,maxn[a[i][j]]+1);
	ans=max(ans,sum);
	for(int j=1;j<=t[i];j++)maxn[a[i][j]]=sum;
}

最后输出 $ans$ 就可以 AC 啦。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,l,a[50001][250],t[50001],maxn[1000001],ans;
inline void init()
{
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		for(int j=1;j*j<=x;j++)if(x%j==0)
		{
			if(j>=l)a[i][++t[i]]=j;
			if(x/j>=l&&j*j!=x)a[i][++t[i]]=x/j;
		}
	}
}
inline void solve()
{
	for(int i=1;i<=n;i++)
	{
		int sum=0;
		for(int j=1;j<=t[i];j++)sum=max(sum,maxn[a[i][j]]+1);
		ans=max(ans,sum);
		for(int j=1;j<=t[i];j++)maxn[a[i][j]]=sum;
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	init(),solve();
	return 0;
}