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
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 Input4 2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2Output 4 3 6 2Input 1 42Output 42Input 2 1 1 1 1Output 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;
}
（编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
