H - To the Park(构造 + 思维)

ZOJ

宝宝和他的(n - 1)个同学要去公园。为了方便，他们的老师DreamGrid将学生从1到n编号，并决定将学生分成几个组，每个组恰好由两个学生组成。出于某种原因，DreamGrid要求同一组的两个学生的指数应该有一个大于1的公约数。请注意，每个学生最多只能属于一个组，并且没有必要每个学生都属于一个组。请帮助DreamGrid组织尽可能多的小组。输入有多个测试用例。输入的第一行包含一个整数T，表示测试用例的数量。对于每个测试用例:第一行也是唯一一行包含一个整数n (1 < n < 105)，表示学生的数量。可以保证所有测试用例的总和n不超过106。输出对于每个测试用例输出一行。这一行首先包含一个整数k，表示组的数量，然后是2k个整数a1, a2， ..， a2k跟随，表示学生a1和a2属于同一组，学生as和a4属于同一组，…，学生a2k-1和azk属于同一组。一行中的整数用空格隔开。如果有多个有效答案，则可以打印其中任何一个。请不要在每行结尾输出额外的空格，否则您的解决方案可能被认为是错误的!

Sample Input

3
1
4
6

Sample Output

0
1 2 4
2 2 4 3 6

题解:

如何构造两两配对且gcd不为1的数,我们应该联想到质数,我们从大到小统计每个质数

遇到质数s,看s到n有几个未使用的s的倍数cnt

如果 cnt为奇数,则从3*s开始存,为了得到更多的配对,为偶数时正常存即可

举个例子7 14 21 28 35

我们应该跳过14,因为对于这五个未使用的数,目前最多有两个配对,所以让14到遍历2的时候存到2里面(同理,对于所有质数都这样)

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
int pri[100050];
int ispri[100050];
int vis[100050];
vector<int> ans[100050];
void solve() 
{
	int n;
	scanf("%d",&n);
	int num = 0;
	for(int i = 1;i <= n;i++)
	{
		ans[i].clear();
		vis[i] = 0;
	}
	for(int i = n;i >= 2;i--)
	{
		if(ispri[i])
		{
			int cnt = 1;
			int s = i;
			vis[i] = 1;
			for(int j = i*2;j <= n;j += i)
			{
				if(!vis[j])
				cnt++;
			}
			if(cnt > 1)
			num++;
			ans[i].push_back(i);
			cnt & 1?s = 3*i:s = 2*i;
			for(int j = s;j <= n;j += i)
			{
				if(!vis[j])
				{
					vis[j] = 1;
					num++;
					ans[i].push_back(j);
				}
			}
		}
	}
	cout <<num/2;
	for(int i = 2;i <= n;i++)
	{
		int len = ans[i].size();
		if(len >= 2)
		{
			for(int j = 0;j < len;j += 2)
			{
				cout <<" "<<ans[i][j]<<" "<<ans[i][j];	
			}
		}
	}
	cout <<"\n";
}
 
//1 2 4
signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
    scanf("%d",&t);
    memset(ispri,1,sizeof ispri);
    ispri[0] = ispri[1] = 0;
    int cnt = 0;
    for(int i = 2;i <= 100000;i++)
    {
		if(ispri[i])
		pri[++cnt] = i;
		for(int j = 1;j <= cnt&&i*pri[j] <= 100000;j++)
		{
			ispri[i*pri[j]] = 0;
			if(i%pri[j] == 0)
			break;
		}
	}
	while (t--) 
	{
		solve();
	}
	return 0;
}
//1 1 1 0 1
 
//1 1 1 0 1
//1 1 1 0 1
//1 1 1 0 1
//0 1 1 1 1
//0 1 1 1 1