BestGrouping

NC215145. BestGrouping

描述

Kotori and her $(n-1)$ classmates are going to the park. For convenience, their teacher Umi has numbered the students from $1$ to $n$ and decides to form the students into some groups, where each group consists of exactly two students.

For some reason, Kotori requires that the indices of the two students in the same group should have a common divisor greater than $1$ . Note that each student can only belong to at most one group, and it's not necessary that every student belongs to a group.

Please help Kotori form as many groups as possible.

输入描述

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:

The first and only line contains an integer  () indicating the number of students.

It's guaranteed that the sum of  of all test cases will not exceed .

输出描述

For each test case output one line. The line first contains an integer  indicating the number of groups, then  integers  follow, indicating that student  and  belong to the same group, student  and  belong to the same group, ..., student  and  belong to the same group. The integers in a line are separated by a space. If there are multiple valid answers, you can print any of them.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!

示例1

输入:

输出:

0
1 2 4
2 2 4 3 6

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 57ms, 内存消耗: 6392K, 提交时间: 2020-12-20 10:18:34

#include<bits/stdc++.h>
using namespace std;
int t,n,ans,q[100050],w[100050],e[100050],r[100050]; 
int main()
{
	for(int i=2;i<=100000;i++)if(q[i]==0)for(int j=i;j<=100000;j+=i)if(q[j]==0)q[j]=i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);ans=0;
		for(int i=2;i<=n;i++)e[i]=r[i]=0;
		for(int i=2;i<=n;i++)w[i]=q[i],e[w[i]]++;
		for(int i=3;i<=n/2;i++)if(e[i]%2)e[2]--,w[i*2]=i,e[i]++;
		for(int i=2;i<=n;i++)ans+=e[i]/2;
		printf("%d",ans);
		if(ans)
			for(int i=2;i<=n;i++)
			{
				if(r[w[i]]==0)r[w[i]]=i;
				else printf(" %d %d",r[w[i]],i),r[w[i]]=0;
			}
		printf("\n");
	}
	return 0;
}

上一题

下一题

详情