302990: CF582A. GCD Table

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:6 Solved:0

Description

GCD Table

题意翻译

## 题目描述 有一个长度为$n$的数列$a$,它可以生成一个$n*n$的数表,数表的第$i$行第$j$列存放的数字是$\gcd(a[i],a[j])$ (即$a[i]$和$a[j]$的最大公因数)。 ![一个例子:](https://cdn.luogu.com.cn/upload/image_hosting/zv3hmpih.png?x-oss-process=image/resize,m_lfit,h_170,w_225) 举个例子,上面那个表,就是由数列$a[]=\{4,3,6,2\}$生成的。 现在我们要做这样一件事情:将这个数表中的这$n*n$ 个数打乱,得到一个长度为$n*n$的序列(可参考样例1)。在已知这个序列的情况下,请还原出数列$a$。 ## 输入格式 第一行是一个整数$n$($1\leq n\leq500$),代表的是原数列$a$的长度。 第二行是$n*n$个整数(均不超过$10^9$,且均为正数),代表打乱之后的数表的元素。保证有解。 ## 输出格式 共一行$n$个整数,即您还原出的数组$a$中的元素。数与数之间用一个空格分隔开。 如果有多个这样的数列$a$满足题意,只需要输出一组即可。

题目描述

The GCD table $ G $ of size $ n×n $ for an array of positive integers $ a $ of length $ n $ is defined by formula ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582A/dfe343d749e54e335e4cc935f51c0cab063fdf0e.png)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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582A/ab5a359df133b7717a6854446e08712b7193aadb.png). For example, for array $ a={4,3,6,2} $ of length 4 the GCD table will look as follows: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582A/f5864be4fb7e459760cc52b428bcbb1eaaf4aca6.png)Given all the numbers of the GCD table $ G $ , restore array $ a $ .

输入输出格式

输入格式


The first line contains number $ n $ ( $ 1<=n<=500 $ ) — the length of array $ a $ . The second line contains $ n^{2} $ 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^{9} $ . 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 $ .

输出格式


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.

输入输出样例

输入样例 #1

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

输出样例 #1

4 3 6 2

输入样例 #2

1
42

输出样例 #2

42 

输入样例 #3

2
1 1 1 1

输出样例 #3

1 1 

Input

题意翻译

## 题目描述 有一个长度为$n$的数列$a$,它可以生成一个$n*n$的数表,数表的第$i$行第$j$列存放的数字是$\gcd(a[i],a[j])$ (即$a[i]$和$a[j]$的最大公因数)。 ![一个例子:](https://cdn.luogu.com.cn/upload/image_hosting/zv3hmpih.png?x-oss-process=image/resize,m_lfit,h_170,w_225) 举个例子,上面那个表,就是由数列$a[]=\{4,3,6,2\}$生成的。 现在我们要做这样一件事情:将这个数表中的这$n*n$ 个数打乱,得到一个长度为$n*n$的序列(可参考样例1)。在已知这个序列的情况下,请还原出数列$a$。 ## 输入格式 第一行是一个整数$n$($1\leq n\leq500$),代表的是原数列$a$的长度。 第二行是$n*n$个整数(均不超过$10^9$,且均为正数),代表打乱之后的数表的元素。保证有解。 ## 输出格式 共一行$n$个整数,即您还原出的数组$a$中的元素。数与数之间用一个空格分隔开。 如果有多个这样的数列$a$满足题意,只需要输出一组即可。

加入题单

上一题 下一题 算法标签: