CodeForces - 582A GCD Table
| Time Limit: 2000MS | Memory Limit: 262144KB | 64bit IO Format: %I64d & %I64u |
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 n2 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 109. 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;
}