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;
}