====== 특이한 수열 ====== ===== 풀이 ===== * n-k개의 수는 서로소가 되고, k개의 수는 서로소가 안되어야 한다. * 차이가 1인 두 수는 서로소가 된다는 사실을 이용하면, 1≤i≤x-1인 i에 대해서 A[i]=i+1 로 정하는 방식으로, 모두 서로소가 되도록 만들수 있다. A[x]=1 로 두면, 1부터 x까지의 수를 사용해서 gcd(i, A[i]) > 1 을 만족하는 i가 한개도 없도록 만들 수 있다. x≤i≤n 까지의 i에 대해서는 A[i]=i가 되도록 하면, 거기에 포함되는 (n-x+1)개 수들은 모두 gcd(i, A[i]) = i > 1를 만족하게 된다. * 그러므로 n-x+1 = k 가 되도록 x를 잡아서 저대로 만들어주면 끝. k=n 일때만 불가능으로 처리해주면 된다. * 시간복잡도는 O(n)이다. ===== 코드 ===== """Solution code for "BOJ 13018. 특이한 수열". - Problem link: https://www.acmicpc.net/problem/13018 - Solution link: http://www.teferi.net/ps/problems/boj/13018 Tags: [ad hoc] """ def main(): n, k = [int(x) for x in input().split()] if n == k: print('Impossible') return answer = [*range(2, n - k + 1), 1, *range(n - k + 1, n + 1)] print(*answer) if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:골드_4}}