차이가 작은 분해
시간 제한3초메모리 제한512 MB
n을 서로 1 이하만큼 차이나는 양의 정수들의 곱으로 나타내는 모든 분해를 나열하고, 무한히 많으면 -1을 출력한다.
문제
리디아는 수를 가지고 노는 것을 좋아한다. 오늘 리디아에게 양의 정수 이 하나 있고, 리디아는 이 수를 양의 정수의 곱으로 분해하려고 한다.
리디아는 크기가 비슷한 수를 좋아한다. 그래서 분해에 쓰인 수는 어느 두 개를 골라도 차이가 1 이하여야 하고, 분해에 쓰인 수를 모두 곱하면 이 되어야 한다. 두 분해는 원소 개수가 같고 한쪽을 재배열해 다른 쪽을 만들 수 있을 때 같은 분해로 본다.
오늘 리디아가 가지고 놀 수 있는 분해를 모두 찾는 프로그램을 작성하시오.
입력
첫째 줄에 정수 이 주어진다. ()
출력
분해가 무한히 많으면 첫째 줄에 만 출력한다.
분해가 유한하면 첫째 줄에 분해의 개수를 출력한다. 다음 줄부터 분해를 한 줄에 하나씩 출력한다. 각 줄에는 그 분해의 원소 개수 를 먼저 출력하고, 이어서 원소 개를 작은 수부터 차례로 출력한다. 수와 수 사이는 공백 하나로 구분한다.
서로 다른 분해는 원소 개수가 항상 다르므로, 줄은 가 작은 것부터 큰 순서로 출력한다.