牛客多校第四场 H-Harder Gcd Problem【素数筛+贪心】

题意

• 链接：Harder Gcd Problem
• 给出一个数列{ 1 ，2 ，…… ，n } ，每次从中取两个不互质的数进行匹配，取过的不能再取，问最多能取多少次，并输出匹配方案（不唯一）

解题思路

• 枚举所有>=2且<=n/2的质因子 p，考虑p 的所有>=3且kp<=n的倍数、且未被匹配的数，任意将它们进行匹配。
• 如果个数是奇数就与 p否则将p与2p匹配。
• 最后把剩下的偶数都随意匹配一下。n以具体的数字为例，方便找到规律，理顺思路。

---

举个具体的例子，n=26，最小素因子是2，为了避免重复，我们只需枚举小于等于n/2的素数：2,3,5,7,13。

求这些素数的倍数（小于等于n），列出表格方便观察，如下：

p	p*2	p*3	p*4	p*5	p*6	p*7	p*8	p*9	p*10	p*11	p*12	p*13
2	4	6	8	10	12	14	16	18	20	22	24	26
3	6	9	12	15	18	21	24
5	10	15	20	25
7	14	21
13	26

不难发现，同一行或者同一列(列>1)的任意两个数字都不互质，可以任意配对。但是在表格中数字会有重复，由于每个数字只能用一次，所以我们要想一个贪心策略来选数。观察上表，可以发现第2列的所有数字都会在第1行再次出现，第2列到第13列中的数字也可能会多次出现，而只有第1列的所有数字只会出现一次。

考虑每一行之间的数字互相配对的方案。
（1）由于第1行（都是偶数）比较特殊，不妨从第2行开始配对，也就是把偶数留下来最后配对。
（2）由于第1列（都是素数，只出现一次）和第2列（都是偶数，并且在第1行再次出现）比较特殊，所以每行的配对都先从第3列开始。
①如果第3列后没被用过的数字个数为奇数个，则将最后一个可行数字与第1列的数字配对。
原因：这样就会留下第2列的数字没配对，没关系，它们都是偶数，那么就一定在第1行出现，只要最后在第1行配对所有没被用过的偶数即可。

②如果第3列后没被用过的数字个数为偶数个，则将第2列的数字与第1列的数字配对。
原因：这里就体现出了贪心策略，因为第2列的数字都在第1行再次出现，也就是说它们可以和第1行的任意数字配对，但是如果那样配对就会消耗第1行的数字，总配对数显然会少于第2列与第1列数字进行配对的方案。应该要留更多的机会让第1行数字互相配对。
（3）最后配对第1行的数字，即配对所有还没被用过的偶数。

引用文章：传送门

---

代码

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int prime[N],vis[N];
vector<int>ans;
void init()
{
	memset(vis,0,sizeof(vis));
	vis[1]=1;int cnt=0;
	for(int i=2;i<=N;i++)
	{
		if(!vis[i])//i是质数 
			prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
		{
			vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
		}
	}
}
int main()
{
	int t,n,c;
	init();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans.clear();
		int maxn=n/2;
		memset(vis,0,sizeof(vis));
		for(int i=2;prime[i]<=maxn;i++)//从第二个素数（第二行）开始枚举
		{
			int p=prime[i],cnt=0;
			for(int j=3;j*p<=n;j++)//从第三列开始枚举 
			{
				int x=j*p;
				if(!vis[x])
				{
					ans.push_back(x);
					vis[x]=1;
					cnt++;
				}
			} 
			if(cnt%2==1)//若该行除前两列外未被选中的数为奇数个，则与第一列的数匹配 
			{
				ans.push_back(p);
				vis[p]=1; 
			}
			else{//若该行除前两列外未被选中的数为偶数个，则第一列与第二列的数匹配 
				ans.push_back(p);
				ans.push_back(p*2);
				vis[p]=1; 
				vis[2*p]=1; 
			}
		} 
		int cnt=0; 
		for(int i=1;i<=maxn;i++)//最后处理第一行剩下的偶数对
		{
			int x=2*i;
			if(!vis[x])
			{
				ans.push_back(x);
				vis[x]=1; 
				cnt++;
			}			
		}
		if(cnt%2==1)ans.pop_back();//若剩余的偶数为奇数个则有一个是不能找到匹配的将最后一个数弹出
		int m=ans.size();
		printf("%d\n",m/2); 
		for(int i=0;i<m;i+=2)
			printf("%d %d\n",ans[i],ans[i+1]);
	}
	return 0;
}