피보나치 수 분석

피보나치 수 F(n)은 다음과 같이 재귀적으로 정의된다.

$$F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2) \ (n \ge 2)$$

정수 구간 [lo, hi]가 주어질 때, 이 구간(양 끝 포함)에 들어가는 모든 피보나치 수를 찾아 각각에 대해 다음 정보를 출력한다.

• 피보나치 수의 인덱스 n과 값 F(n)
• 그 값의 밑이 2인 로그 lg (소수점 여섯째 자리까지)
• 그 값의 소인수분해 (오름차순, 중복된 소인수는 나타나는 횟수만큼 출력)

단, 다음 규칙을 따른다.

• 0은 첫 번째 피보나치 수이지만 0의 로그는 정의되지 않으므로, 로그 대신 lg does not exist를 출력한다.
• 0과 1은 소인수가 없으므로, 소인수분해 대신 No prime factors를 출력한다.
• 구간에 들어가는 피보나치 수가 하나도 없으면 No Fibonacci numbers in the range를 출력한다.

F(1) = 1과 F(2) = 1처럼 인덱스는 다르지만 값이 같은 피보나치 수는 각각 따로 출력한다.

입력은 여러 개의 구간으로 이루어지며, 각 구간은 한 줄에 음이 아닌 두 정수 lo와 hi로 주어진다. 두 수는 접두사 0x가 붙은 16진수로 표기된다. 예를 들어 0x1a는 26을 뜻한다.

각 정수는 64비트 부호 있는 정수 범위에 속한다. 파일의 끝(EOF)에 도달하거나 어떤 줄에서 lo ≥ hi이면 입력을 종료한다. (종료 조건에 해당하는 줄은 처리하지 않는다.)

처리하는 각 구간마다 먼저 구간을 나타내는 머리글 Range {lo} to {hi}:를 십진수로 출력한다. 이어서 구간에 들어가는 각 피보나치 수에 대해 아래 형식으로 두 줄씩 출력한다.

• 첫째 줄: Fib({n}) = {값}, lg is {로그} (값이 0이면 Fib({n}) = 0, lg does not exist)
• 둘째 줄: Prime factors: {소인수들} (값이 0 또는 1이면 No prime factors)

밑이 2인 로그(lg)는 소수점 여섯째 자리까지 출력하고, 소인수는 공백으로 구분한다. 서로 다른 구간의 출력은 빈 줄 하나로 구분한다.