테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 특이한 수열 ======

===== 풀이 =====
  * 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)이다.


===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}