题目描述

给出n个数，将这n个数进行分组，分组规则为：除了1以外最小的约数相同的数字分为一组。最后，输出这个最小约数，同时按照从小到大的顺序逐一输出这些数字。

例如：7个数，35 8 39 12 8 26 25 输出为：

2 8 8 12 26（[8, 8, 12, 26]为给定的7个数中，以2为最小约数（除1以外）的数） 3 39（[39]为给定的7个数中，以3为最小约数（除1以外）的数） 5 25 35（[25， 35]为给定的7个数中，以5为最小约数（除1以外）的数）

输入格式

第一行：1个数n（n <= 10000） 后面n行，每行1个数a[i]（2 <= a[i] <= 100000）

输出格式

按照约数d从小到大的顺序，逐行输出所有最小约数（除了1之外的）为d的数字，并且每行中输出数字的顺序也是从小到大。

样例数据

input

7
35
8
39
12
8
26
25

output

2 8 8 12 26
3 39
5 25 35

蒟蒻代码：

set版

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
inline int read()
{
	short f=1;
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	{x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,a[10010],maxx,vis[100010];
multiset<int>s;
multiset<int>::iterator it;
signed main()
{
	freopen("classify.in","r",stdin);
	freopen("classify.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)	a[i]=read(),maxx=max(maxx,a[i]);
	for(int i=2;i<=maxx;i++)
	{
		if(vis[i])	continue;
		s.clear();
		for(int j=i*i;j<=maxx;j+=i)	if(!vis[j])	vis[j]=i;
		for(int j=1;j<=n;j++)	if(vis[a[j]]==i||a[j]==i)	s.insert(a[j]);
		if(s.empty())	continue;
		printf("%d ",i);
		for(auto j:s)	printf("%d ",j);
		printf("\n");
	}
	return 0;
}

vector版

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
inline int read()
{
	short f=1;
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	{x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,a[10010],maxx,vis[100010];
vector<int>s;
vector<int>::iterator it;
signed main()
{
	freopen("classify.in","r",stdin);
	freopen("classify.out","w",stdout);
	n=read();
	for(int i=0;i<n;i++)	a[i]=read(),maxx=max(maxx,a[i]);
	for(int i=2;i<=maxx;i++)
	{
		if(vis[i])	continue;
		s.clear();
		for(int j=i*i;j<=maxx;j+=i)	if(!vis[j])	vis[j]=i;
		for(int j=0;j<n;j++)	if(vis[a[j]]==i||a[j]==i)	s.push_back(a[j]);
		if(s.empty())	continue;
		printf("%d ",i);
        sort(s.begin(),s.end());
		for(it=s.begin();it!=s.end();it++)	printf("%d ",*it);
		printf("\n");
	}
	return 0;
}

得分：均为70 3个点RE

蒟蒻求助