Codeforces 582A

发表于 |

题目

长度为$N$的数列{a_i}的GCD Table定义为一个$N\times N$的表，表中元素$b_{ij}=gcd(a_i,a_j)$。
现给你一个GCD Table中的所有数，要求输出原数列中的所有元素。

数据范围

$N \leq 500$

做法

注意到：$gcd(a,b)≤min(a,b)$ 。

所以，最大的$gcd$值一定在原数列中出现，将此数从所给的数中去掉。剩下的数中，最大的数也一定在原数列中。将此数从所给的数中去掉，再将此数与之前得出的原数列中的数的$gcd$从所给的数中去掉。不断重复此过程，直到所给的数都被去掉。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 505;
int N, a[MAX_N * MAX_N];
vector<int> ans;
map<int, int> mp;
map<int, int>::iterator it;
int main()
{
	cin >> N;
	for (int i = 0; i < N * N; ++i) scanf("%d", a + i), mp[-a[i]]++;
	it = mp.begin();
	ans.push_back(-it->first); --(it->second);
	for (; ;) {
		while (it->second == 0) {
			it++;
			if (it == mp.end()) break;
		}
		if (it == mp.end()) break;
		for (int i = 0; i < (int)ans.size(); ++i) {
			mp[-__gcd(ans[i], -it->first)] -= 2;
		}
		ans.push_back(-it->first);
		--(it->second);
	}
	for (int a : ans) printf("%d ", a);
	puts("");
	return 0;
}