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