CodeForces – 582A GCD Table （map大数操作amp;gcd）好题

CodeForces – 582A

GCD Table

SubmitStatus

Description

The GCD table G of size n?×?n for an array of positive integers a of length n is defined by formula

Let us remind you that the greatest common divisor (GCD) of two positive integers x and y is the greatest integer that is divisor of both x and y,it is denoted as

. For example,for array a?=?{4,?3,?6,?2} of length 4 the GCD table will look as follows:

Given all the numbers of the GCD table G,restore array a.

Input

The first line contains number n (1?≤?n?≤?500) — the length of array a. The second line contains n² space-separated numbers — the elements of the GCD table of G for array a.

All the numbers in the table are positive integers,not exceeding 10⁹. Note that the elements are given in an arbitrary order. It is guaranteed that the set of the input data corresponds to some array a.

Output

In the single line print n positive integers — the elements of array a. If there are multiple possible solutions,you are allowed to print any of them.

Sample Input

Input

4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2

Output

4 3 6 2

Input

1
42

Output

42 

Input

2
1 1 1 1

Output

1 1 

Sample Output

Hint

Source

Codeforces Round #323 (Div. 1)

//题意：输入n，再输入n*n个数

表示给你n个数的gcd表，让你求出这n个数分别是什么。

//思路：

可以将这n*n个gcd的值从小到大排序，再从后往前找，先找到最大的，再根据找到的大的值通过排除法排除掉重复的值，这样一直遍历下去就行了。

Hait:最大的那个数肯定是a[n*n],因为这是它自身与自身的gcd得到的值。因为数很大10^9,所以得用map来计数。

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<iostream>
#define N 510
using namespace std;
int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}
map<int,int>m;
int a[N*N],ans[N];
int main()
{
	int n,i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		m.clear();
		for(i=1;i<=n*n;i++)
		{
			scanf("%d",&a[i]);
			m[a[i]]++;
		}
		sort(a+1,a+n*n+1);
		int top=0;
		for(i=n*n;i>=1;i--)
		{
			if(!m[a[i]])
				continue;
			ans[top++]=a[i];//最大的肯定是自身与自身的gcd 
			m[a[i]]--;
			for(j=0;j<top-1;j++)
				m[gcd(ans[j],a[i])]-=2;//由表可知，它是对称的，所以 要减去2 
		}
		for(i=0;i<top;i++)
			printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}