제곱 함수

시간 제한2초메모리 제한256 MB

요약

주어진 y에 대해 S(x)가 y가 되는 모든 x를 구합니다. S(x)는 x에서 시작해 곱이 완전제곱수가 되는 증가하는 수열의 마지막 원소 중 가장 작은 값입니다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

함수 $S: \mathbb{N} \rightarrow \mathbb{N}$ 를 다음과 같이 정의한다. $S(x)$ 는 증가하는 정수 수열 $x = t_1 < t_2 < \ldots < t_k = S(x)$ 가 존재하도록 하는 가장 작은 수이다. 이때 곱 $t_1 \cdot t_2 \cdot \ldots \cdot t_k$ 는 어떤 정수의 제곱이어야 한다. 예를 들어 $S(2) = 6$ , $S(3) = 8$ , $S(4) = 4$ 이다.

$y$ 가 주어졌을 때, $S(x) = y$ 를 만족하는 모든 $x$ 를 구하시오.

입력

첫 번째 줄에 정수 $y$ ( $1 \le y \le 10^{6}$ )가 주어진다.

출력

첫째 줄에 해의 개수를 출력한다. 둘째 줄에는 해를 증가하는 순서로 공백으로 구분하여 출력한다.

힌트

$\mathbb{N}$ 은 양의 정수의 집합이다.

예제3

예제 1
입력
```
4
```
예상 출력
```
1
4
```
예제 2
입력
```
5
```
예상 출력
```
0
```
예제 3
입력
```
6
```
예상 출력
```
1
2
```