bzoj 2632: [neerc2011]Gcd guessing game【贪心】

这个告诉gcd的操作实际上就是告诉一个因数是否选，最坏情况是1，判断掉所有因数才能选

然后肯定是用猜不重复质数积比较划算，问题就变成若干个质数，分成数量尽量小每组乘积<=n的若干组

从大质数开始，贪心的选尽量多的小质数和他乘起来，原理是反正大质数都要分进一组，能多带流多带

#include<iostream>

#include<cstdio>

using namespace std;

const int N=10005;

int n,p[N],tot,ans;

bool v[N];

int main()

{

	scanf("%d",&n);

	v[1]=1;

	for(int i=2;i<=n;i++)

	{

		if(!v[i])

			p[++tot]=i;

		for(int j=1;j<=tot&&i*p[j]<=n;j++)

		{

			v[i*p[j]]=1;

			if(i%p[j]==0)

				break;

		}

	}

	for(int i=tot,l=1;i>=l;i--)

	{

		ans++;

		int x=p[i];

		while(l<i&&x*p[l]<=n)

			x*=p[l++];

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 2632: [neerc2011]Gcd guessing game【贪心】

最新文章

热门文章