BOJ 34967 최대공약수 완충재

일단, 문제의 조건을 충족하는 길이 20000의 수열을 하나 찾으면 길이 $N$의 수열은 그 중 앞의 $N$개를 출력하면 됨을 알 수 있습니다. 그리고 최대공약수가 모두 서로 다르게 하기 위해서는 최대공약수의 값들이 1, 2, …, 19999 중 하나를 가져야 할 것이라고 추측할 수 있습니다.

이제 이웃한 두 수들의 최대공약수의 나열을 $g_1, g_2, \cdots, g_{19999}$라고 합시다. 양쪽 끝을 제외하고, $A_i$는 $LCM(g_{i-1}, g_i)$의 배수여야 합니다. 편의상 $A_i = g_{i-1} \times g_i$로 두면 적당할 것이라고 추측할 수 있습니다. 양쪽 끝 값은 $A_1 = g_1$, $A_{20000} = g_{19999}$로 둘 수 있습니다.

여기서 이웃한 두 수들의 최대공약수가 실제로 $g_1, g_2, \cdots$일 조건을 찾아봅시다. $GCD(A_i, A_{i+1}) = GCD(g_{i-1}g_i, g_i g_{i+1}) = g_i GCD(g_{i-1}, g_{i+1})$ 이므로, 이 GCD 값이 $g_i$일 조건은 $g_{i-1}$과 $g_{i+1}$이 서로소임이 됩니다. 이 조건들을 모두 연결하면 두 개의 체인이 만들어지며, 예를 들어 짝수번째 자리에 1부터 9999까지, 홀수번째 자리에 10000부터 19999까지를 배정하면 GCD 조건을 충족합니다.

마지막으로 $A_i$의 범위 조건을 충족하기 위해, 두 값을 곱한 값이 1억 이하로 유지되도록 짝수번째 GCD들의 순서를 뒤집어주면 문제의 답이 됩니다.