BOJ 12972 GCD 테이블
알고리즘 문제풀이/BOJ
2019. 9. 13. 23:10
문제 : 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$ 중 가장..