Yukicoder No. 14 最小公倍数ソート

Yukicoder No. 14 최소공배수 정렬

문제 링크

문제

최소공배수를 막 배운 Larry는, 최소공배수 정렬을 하기로 했습니다.

여기서, "최소공배수 정렬"은,
$N$개의 정수가 주어지고(중복을 포함할 수 있습니다), 각각을 $a_i \ ( 1 \le i \le N)$이라고 합시다.
$a_1$을 고정하고, $a_2 \sim a_N$에 대해 각각 $a_1$과의 최소공배수를 구해서, 그 최소공배수가 작은 순으로 수열을 정렬합니다.
(최소공배수가 같은 것이 여럿 있으면, 원래 수가 작은 것을 우선으로 합니다)

Larry는,
이런 방식으로 정렬한 수열에 새로 $a_1 \cdots a_N$이란 이름을 붙이고, 조작을 계속합니다.
다음에는 $a_2$를 고정해서 ($a_1$도 고정한다), $a_3 \sim a_N$을 "최소공배수 정렬"합니다.
다음에는 $a_3$를 고정해서... 를 반복해서 $a_N$까지 반복했을 때 최종 수열을 출력합니다.

입력

$1$번째 줄에는 수열의 길이를 나타내는 정수 $N \ (1 \le N \le 10000)$이 주어집니다.
$2$번째 줄에는 각 정수 $a_i \ (1 \le i \le N, 1 \le a_i \le 10000)$이 공백으로 구분되어 주어집니다.

 

(역자 주: 이 문제는 $O(\max(N, a_i)^2)$ 시간 복잡도 미만에 풀리는 문제입니다.)

출력

$a_1$부터 $a_N$까지 최소공배수 정렬을 반복했을 때의 결과를 공백으로 구분하여 출력해주세요.
마지막에 개행문자를 넣어주세요.

풀이

힌트 1

두 수 $A$와 $B$의 최소공배수는, $\dfrac{AB}{\gcd(A, B)}$로 구할 수 있습니다.

힌트 2

어떤 수 $A$가 정해지면, 남은 수 중에서 $A$와의 최대공배수가 가장 작은 수의 후보로 가능한 것을 생각 해 봅시다.

힌트 3

$A$와의 최대공배수가 가장 작은 수로 가능한 것은, $\gcd(A, B)$를 정해놓고 해당 최대공약수로 가능한 $B$ 중에서 가장 작은 것만이 $A$와의 최대공배수가 가장 작은 수의 후보로 가능하게 됩니다.

풀이

$g$가 $A$와 $B$의 공약수가 되기 위해서는, $B$가 $g$의 배수여야 하고, 동시에 $g$가 $A$의 약수여야 합니다.
모든 $A$의 약수들에 대해 $g$를 고정합시다. 그리고, 각각에 대해 가능한 $g$의 배수로 가능한 $B$의 최솟값을 찾아 봅시다.
$g$의 배수로는 $g, 2g, 3g, \cdots$가 있습니다. 여기서 $g$를 먼저 확인 해 보고, $2g$를 확인 해 보고, ... 이를 반복하면 조건을 만족하는 $B$를 찾을 수 있습니다.
이것을 그냥 구현하면 오래 걸리기 때문에, 우리는 이미 봤던 수를 다시 보지 않는 방법을 사용할 것입니다.
$g$의 배수로 $kg$를 확인해 봤는데, 없었으면 그다음 다른 $A'$이 정해졌을 때도 $kg$를 확인하면 없을 것입니다. 그래서 각 $g$마다 현재 어디까지 확인했는지의 여부를 가지고 있으면 됩니다.
모든 $g$에 대해서 $M = 10000$ 이하의 $g$의 배수 개수는 $O(M \log M)$이기 때문에, 문제를 총 $O(N + M \log M)$ 시간 안에 해결할 수 있습니다.

 

코드: https://yukicoder.me/submissions/732370
해당 구현체는 $A$의 약수를 $\sqrt A$ 이하의 수로 모두 나눠보는 방법을 사용하기 때문에, $O(N + M \sqrt M)$ 시간이 듭니다.