수열

우리는 양의 정수들이 나열된 수열 을 구하는 다음과 같은 두 문제를 풀려고 한다. 수열의 길이는 수열에 포함된 정수들의 개수 \(n\)이라고 정의한다.

문제 \(A\): 양의 정수 \(M\)이 주어질 때, \(a_{1}\)+\(a_{2}\)+...+\(a_{n}=M\)을 만족하면서 \(a_{1}\)×\(a_{2}\)×...×\(a_{n}\)의 값이 가장 크게 되는 수열 을 구하시오. 단, \(a_{1}\)×\(a_{2}\)×...×\(a_{n}\)의 값이 가장 크게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 \(n\)이 최대인 수열을 구하시오.

문제 \(B\): 양의 정수 \(M\)이 주어질 때, \(a_{1}\)×\(a_{2}\)×...×\(a_{m}=M\)을 만족하면서 \(a_{1}\)+\(a_{2}\)+...+\(a_{m}\)의 값이 가장 작게 되는 수열 을 구하시오. 단, \(a_{1}\)+\(a_{2}\)+...+\(a_{m}\)의 값이 가장 작게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 \(m\)이 최소인 수열을 구한다.

문제 \(A\)에서 구한 수열의 길이 \(n\)과 문제 \(B\)에서 구한 수열의 길이 \(m\)을 출력하는 프로그램을 작성하시오.

예를 들어, \(M=6\)이면, 문제 \(A\)에서 구한 수열은 <3,3>이므로 이 수열의 길이는 2이고, 문제 \(B\)에서 구한 수열은 <2,3>이므로 이 수열의 길이는 2이다.

첫째 줄에 정수 \(M\)이 주어진다. \(1 \le M \le 1{,}000{,}000\) 이다.

첫째 줄에 문제 \(A\)에서 구한 수열의 길이 \(n\)과 문제 \(B\)에서 구한 수열의 길이 \(m\)을 한 개의 빈칸을 사이에 두고 차례대로 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2006 > 2차 대회 > 중등부 1번