만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

차이가 작은 분해

시간 제한3초메모리 제한512 MB

요약
n을 서로 1 이하만큼 차이나는 양의 정수들의 곱으로 나타내는 모든 분해를 나열하고, 무한히 많으면 -1을 출력한다.
난이도

보통10점 중 6점

유형
정수론, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

리디아는 수를 가지고 노는 것을 좋아한다. 오늘 리디아에게 양의 정수 nn이 하나 있고, 리디아는 이 수를 양의 정수의 곱으로 분해하려고 한다.

리디아는 크기가 비슷한 수를 좋아한다. 그래서 분해에 쓰인 수는 어느 두 개를 골라도 차이가 1 이하여야 하고, 분해에 쓰인 수를 모두 곱하면 nn이 되어야 한다. 두 분해는 원소 개수가 같고 한쪽을 재배열해 다른 쪽을 만들 수 있을 때 같은 분해로 본다.

오늘 리디아가 가지고 놀 수 있는 분해를 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 nn이 주어진다. (1≤n≤10181 \le n \le 10^{18})

출력

분해가 무한히 많으면 첫째 줄에 −1-1만 출력한다.

분해가 유한하면 첫째 줄에 분해의 개수를 출력한다. 다음 줄부터 분해를 한 줄에 하나씩 출력한다. 각 줄에는 그 분해의 원소 개수 kk를 먼저 출력하고, 이어서 원소 kk개를 작은 수부터 차례로 출력한다. 수와 수 사이는 공백 하나로 구분한다.

서로 다른 분해는 원소 개수가 항상 다르므로, 줄은 kk가 작은 것부터 큰 순서로 출력한다.

예제3

  1. 예제 1

    입력
    12
    
    예상 출력
    3
    1 12
    2 3 4
    3 2 2 3
    
  2. 예제 2

    입력
    1
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    36
    
    예상 출력
    4
    1 36
    2 6 6
    3 3 3 4
    4 2 2 3 3