牛客Harder Gcd Problem

题目链接

题意:

在1-n的整数中每次选取两个不互质的数,求最多能选多少对?

分析:

对于两个不互质的数,情况有两种:

  1. 质数与它的倍数
  2. 两个相同质数的倍数

这两种情况都与一个质数有关,所以可以从每个质数来出发,将它的不同倍数两两配对。(大于n/2的质数必定没得匹配,下面均未考虑

而容易想到,必定得先满足较大的质数,因为如果先取小质数,那么大质数到时候可能就没有匹配了。例如:2和5,如果先取2的各个倍数,10就会被2用掉,如果n=10,5就没有数与他匹配,就用不掉了。
而如果从大到小来,每个质数至少有自己的二倍可以匹配,都能保证被匹配完。

具体方法:

按质数从大到小,每次取出该质数的倍数,如果是偶数个,就可以直接两两配对。如果是奇数个,可以将质数的2倍排除,剩余两两配对。(其实不一定选2,但是由于2是最小的质数,处理起来最简单,所以选2。比如选3会出现一个问题:当前质数为3且是奇数个时,排除3*3=9,会导致9之后便无法匹配,但是在质数为3时排除2倍,别的排除3倍也是可以的。而全部排除两倍的作用保证了排除的那个数最后总能在2的倍数的匹配中)
到了这里基本上就可以明白为什么这个策略得到的是最优解了:从后往前将所有质数的倍数匹配,无法匹配的全留给2来处理,相当于筛法一样筛出了所有可行的匹配。

AC代码:
#includeiostream
#includealgorithm
#includevector
#includeutility
using namespace std;
const int MAX_N = 2e5 + 5;
typedef pairint, int pint;
bool vis[MAX_N];
bool isnotprime[MAX_N];
int prime[MAX_N];
int main()
{
	isnotprime[0] = isnotprime[1] = true;
	for (int i = 2; i  MAX_N; i++)
	{
		if (!isnotprime[i])prime[++prime[0]] = i;
		for (int j = 1; j = prime[0]  i * prime[j]  MAX_N; j++)
		{
			isnotprime[i * prime[j]] = true;
			if (i % prime[j] == 0)break;
		}
	}
	int T;
	cin  T;
	while (T--)
	{
		fill(vis, vis + MAX_N, false);
		int n;
		cin  n;
		int index = upper_bound(prime + 1, prime + prime[0] + 1, n / 2)-prime;
		vectorpint ans;
		for (int i = index-1; i = 1; i--)
		{
			vectorint now;
			for (int j = prime[i]; j = n; j+=prime[i])
				if (!vis[j])now.push_back(j);
			if (now.size() == 1)continue;
			if (now.size()  1)now.erase(now.begin() + 1);//如果是奇数,那么他的2倍一定存在,因为他的二倍不可能被选掉
			/*上面if中的语句也可以写成这样
			if (prime[i] == 3)now.erase(now.begin() + 1);
			else now.erase(now.begin() + 2);
			*/
			for (int j = 0; j+1  now.size(); j+=2)
			{
				ans.push_back(pint(now[j], now[j + 1]));
				vis[now[j]] = vis[now[j + 1]] = true;
			}
		}
		cout  ans.size()'\n';
		for (int i = 0; i  ans.size(); i++)
		{
			cout  ans[i].first  " "  ans[i].second  '\n';
		}
	}
	return 0;
}
最新回复(0)
/jishu083Png9fdXDkch_2Bs_2FD643HFqAzSTvCxtVYL_2Fag_3D_3D4794741
8 简首页