BOJ 12972 GCD 테이블

문제 : BOJ 12972

Codeforces Round #323 A번과 같은 문제. (그림까지 같은걸로 보아 이 문제를 번역한 것 같다)

 

 

문제  

어떤 수열 $a_1, a_2, \dots a_n$ 이 주어질 때, $\gcd(a_i, a_j)$ 들을 모두 모아 $n \times n$ 테이블을 만들고 그걸 다시 흩어놓은 $n^2$개짜리 수열을 생각하자. 이때, 이 수열 $b_1, b_2 \dots b_{n^2}$ 를 보고 원래 수열을 복원할 수 있을까?

---

풀이

어차피 수열 $a$를 복원할 때 순서는 중요하지 않으므로, 편의상 $a$가 정렬되어 있다고 생각하자. ㄷ

또한, $\gcd(a_i, a_j) \leq \min(a_i, a_j)$ 이고, $\gcd(a_i, a_i) = a_i$ 이므로, $b_i$ 중 가장 큰 값은 $\gcd(a_n, a_n) = a_n$ 이다.

$b$ 수열에서 이 값은 위치를 찾았으므로 지우면 된다.  (map erase 같은걸 쓸 수 있다.)

그 다음 값은 $\gcd(a_{n-1}, a_{n-1}) = a_{n-1}$ 이다. 남은 값들로 이보다 큰 gcd를 만들 수 없으므로, 아까 지운 값을 제외하고 가장 큰 값이 $a_{n-1}$ 이다. 이제 $a_{n-1}$ 과 $a_{n}$ 를 찾았으니 $\gcd(a_{n-1}, a_n)$ 도 두 번 (순서 바뀔 수 있으므로) 지워 줄 수 있고, 그러면 다시 $a_{n-2}$ 가 가장 큰 값이 된다.

 

이를 계속 반복하면 원래의 수열을 얻을 수 있고, 각각 한 번씩 gcd 찾고 ($O(\log M)$,  $M$은 수열에서 가장 큰 수), map erase 하고 ($O(\log n)$), 이를 최대 $n^2$번 정도 해야 하므로 대략 전체 시간복잡도 $O(n^2 \log n)$ 정도에 풀 수 있다.

 

코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using namespace std::chrono;
using pii = pair<int, int>;
 
map <int, int> m;
vector <int> a;
vector <int> ans;
int main()
{
	usecppio
	int n;
	cin >> n;
	a.resize(n*n);
	for (int i = 0; i<(n*n); i++)
	{
		cin >> a[i];
		m[a[i]]++;
	}
	sort(all(a));
	int ct = 0;
	int cnt = n*n;
	ans.push_back(a[n*n-1]);
	ct++;
	cnt--;
	m[ans[0]]--;
	if (m[ans[0]]==0)
		m.erase(ans[0]);
	while(!m.empty())
	{
		int x = m.rbegin()->first;
		m[x]--;
		if(m[x]==0)
			m.erase(x);
		for (int i = 0; i<ct; i++)
		{
			m[__gcd(ans[i],x)]-=2;
			if (m[__gcd(ans[i],x)]==0)
				m.erase(__gcd(ans[i],x));
			cnt-=2;
		}
		ans.push_back(x);
		ct++;
	}
	for (auto it:ans)
	{
		cout << it << ' ';
	}
}