P4411 [BJWC2010] 取数游戏题解

博客园可能食用更佳。

给定 $n$ 个数 $a_{1,2,\dots,n}$ ，你需要从左到右按顺序取出一些数，第一个数任取，钦定目前取的数为 $a_j$ ，下一个取的数为 $a_k$ ，需满足 $\gcd(a_j,a_k) \geq L$ ，求最大化取出数的数量。

钦定

V

为

a_i

的最大值，记

f_j

表示约数为

j

时最大的答案数量，每次

\mathcal O(\sqrt a_i)

枚举

a_i

的约数，将

\geq L

的数取出来更新答案即可，最终答案即为

\max_{j=L}^{V} f_j

，时间复杂度为

\mathcal O(n \sqrt V)

，空间复杂度为

\mathcal O(V)

。

CPP

const int N=5e4+5,M=1e6+5;
int n,lim,f[M];
vector<int> a[N];
int main()
{
	read(n),read(lim);
	for(int i=1;i<=n;i++)
	{
		int x; read(x);
		for(int j=1;j*j<=x;j++)
			if(x%j==0)
			{
				if(j>=lim) a[i].pb(j);
				if(j*j!=x&&x/j>=lim) a[i].pb(x/j);
			}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int res=0;
		for(auto x:a[i]) chkmax(res,f[x]+1);
		chkmax(ans,res);
		for(auto x:a[i]) f[x]=res;
	}
	write(ans);
	return 0;
}

P4411 [BJWC2010] 取数游戏题解

文章操作

相关推荐

评论

P4411 [BJWC2010] 取数游戏题解