X-인수 체인 > 문제은행



문제은행

1119 : X-인수 체인

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 8 회    시도횟수: 22 회   



양의 정수 X에 대해 길이가 m이고 X-인수 체인이라 함은 다음을 말한다.
1 = X0,  X1,  X2,  …, Xm = X(이를 설명하면, X0 = 1,  Xm = X 라는 뜻이며 X1 , ... Xm-1 : 임의의 양의 정수를 뜻한다.)

 

위의 X-인수 체인에 존재하는 숫자는 아래의 조건을 만족해야 한다.
Xi < Xi+1 ,    Xi | Xi+1(a|b라는 것은 a가 b를 완전히 나누어 떨어지게 한다는 것이다.)

 

정수 X를 입력받아 X-인수 체인의 최대 길이와, 최대 길이를 이루는 체인이 몇 가지 있는지 알아보는 프로그램을 작성하라.




입력은 20,000,000 이하의 정수 N이 입력된다.



입력에 대해 가장 긴 길이를 이룰 경우의 m과 이러한 경우가 몇 가지인지를 뜻하는 경우의 수를 출력한다.


10
2 2


출처 : poj 3421




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.