수학

시간 제한1초메모리 제한1024 MB

요약

정수 n이 주어질 때, 2 이상 n 이하의 각 k에 대해 앞 k개 항의 합이 a_k개의 양의 약수를 갖도록 1 이상 300 이하의 수열을 찾습니다. 없으면 Impossible을 출력합니다.

난이도: 보통10점 중 5점
유형: 정수론, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

안드로이드 바샤는 수학 수업을 듣는다. 그의 조는 최근 정수론을 공부하기 시작했다. 선생님은 숙제로 여러 과제를 냈고, 그중 하나는 다음과 같다.

정수 $n$ 이 주어진다. 정수 수열 $a_1, \ldots, a_n$ 을 찾는 것이 문제다. 이 수열은 2 이상 $n$ 이하의 모든 $k$ 에 대해 $a_1 + \ldots + a_k$ 의 서로 다른 양의 약수가 정확히 $a_k$ 개이어야 한다. 바샤가 이 과제를 풀도록 도와라.

입력

한 줄에 정수 $n$ ( $2 \leq n \leq 100\,000$ )이 주어진다.

출력

그러한 수열이 없으면 Impossible을 출력한다. 있으면 공백으로 구분한 정수 $a_1, \ldots, a_n$ ( $1 \leq a_i \leq 300$ )을 출력한다.

예제1

예제 1
입력
```
3
```
예상 출력
```
1 3 4
```