언젠가 정렬이 될 수 있으면 좋겠네.

사전 순 최소는 앞 원소부터 가능한 작은 수로 채우는 것이 최적입니다.

현재 사전 순 최소인 수열을 $k$번째까지 완성했고, 다음 원소를 결정할 차례라고 해봅시다.

$T_i =$ 남은 수 중 $A_i$보다 앞에 있으면서 $A_i$와 서로소가 아닌 수의 개수 라고 정의하겠습니다.

처음에 $T$ 배열은 $cal(O)(N^2 log X)$에 구성할 수 있습니다.

자신보다 앞에 있는 수 중 자신과 서로소가 아닌 것이 있다면 자신은 맨 앞으로 이동할 수 없습니다.

따라서 남은 수 중 다음 원소가 될 수 있는 것은 $T_i = 0$ 인 $A_i$입니다.

이러한 $A_i$들 중 가장 작은 수를 다음 원소로 결정하는 것이 최적입니다.

$A_p$를 다음 원소로 결정했다면, $p < q$ 이고 $A_p$와 $A_q$가 서로소인 모든 $q$에 대해 $T_q$를 $1$ 감소시킬 수 있습니다.

이를 총 $N$번 반복하면 사전 순으로 최소인 수열을 얻을 수 있습니다.

전체 시간복잡도는 $cal(O)(N^2 log X)$입니다.

삽입 정렬과 유사하게 진행하는 풀이도 있습니다.

수열 $A$의 앞 $k - 1$개의 원소들만으로 사전 순 최소를 만들었고, $A_k$를 적절한 위치에 끼워넣는 상황을 생각해봅시다.

$A_k$가 $A_i$보다 작으면서 그 사이의 모든 수가 $A_k$와 서로소라면 $A_k$를 $A_i$ 자리에 삽입할 수 있고, 이러한 위치 중 가장 앞을 택하는 것이 최적입니다.

이를 총 $N$번 반복하면 사전 순으로 최소인 수열을 얻을 수 있습니다.

위의 증명은 독자의 몫으로 남깁니다.