사용자 도구

사이트 도구


ps:problems:boj:13018

특이한 수열

ps
링크acmicpc.net/…
출처BOJ
문제 번호13018
문제명특이한 수열
레벨골드 4
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=10^5
사용한 언어Python 3.13
제출기록37928KB / 72ms
최고기록52ms
해결날짜2025/04/03

풀이

  • 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()

토론

댓글을 입력하세요:
F T X H U
 
ps/problems/boj/13018.txt · 마지막으로 수정됨: 2025/04/03 14:17 저자 teferi