「BOJ 4463」 피보나치 수 분석

링크

• 4463번: 피보나치 수 분석

---

문제

어떤 피보나치 수는 좀비의 공격에 면역성이 있다. 그 이유는 소수는 분해할 수 없기 때문이다.

피보나치 수는 아래와 같이 재귀적으로 정의할 수 있다.

64비트 부호있는 정수로 표현할 수 있는 정수 범위가 주어진다. 이때, 그 구간에 포함되는 피보나치 수를 찾은 다음, 그 수의 밑이 2인 로그를 취한 값과 소인수 분해를 하는 프로그램을 작성하시오. 소인수는 오름 차순이며, 여러 번 등장하는 수는 그만큼 출력해야 한다. 만약, 그 구간에 해당하는 피보나치 수가 없는 경우에는 없다고 출력하면 된다.

 

0은 첫 번째 피보나치 수이지만, 0의 로그는 정의되지 않는다. 또, 0과 1은 소인수가 없다.

입력

첫째 줄에 구간을 나타내는 음이 아닌 두 정수 \( lo \) 와 \( hi \) 가 주어진다. 두 수는 16진수 표현 (0x1a 는 26)으로 주어진다. 각 정수는 모두 64비트 부호있는 정수 범위이며, 파일의 끝(EOF)이나 \( lo \geq hi \) 인 경우에 종료한다.

출력

입력으로 주어지는 각 구간에 대해서, 구간을 출력한 다음 예제 출력과 같이 피보나치 수에 대한 정보를 출력한다. 각 구간은 빈 줄로 나누어져 있어야 한다.

밑이 2인 로그(lg)는 소수점 여섯째 자리 까지 출력하며, 소인수는 공백으로 구분한다.

---

풀이

\( 2^{63} - 1 \) 아래의 피보나치 수를 모두 구하고 소인수분해해야 하는 문제입니다. 워낙 큰 수라서 숨이 턱 막힐 수도 있지만, 다음 요소들을 잘 고려하면서 코드를 짜준다면 이 문제를 해결할 수 있습니다.

 

• 16진수 표현 (0x ...) 으로 주어지는 입력 처리
• \( 2^{63} - 1 \) 이하의 피보나치 수들 구하기
• 해당 피보나치 수들의 로그(lg) 값과 소인수들 구하기

 

i) 16진수 표현 (0x ...) 으로 주어지는 입력 처리

Python에서는 문자열로 입력받은 후 ___bulitin__ 에 있는 int(str, base=16) 으로 간단하게 처리할 수 있습니다. \( lo \geq hi \) 인 경우와 EOF를 만난 경우도 추가적으로 잘 처리해주시면 됩니다.

 

ii) \( 2^{63} - 1 \) 이하의 피보나치 수들 구하기

생각보다 이 범위 안의 피보나치 수들이 많지 않습니다. 직접 fibo[i] = fibo[i-1] + fibo[i-2] 등의 방법으로 구하셔도 괜찮습니다.

 

ii) 해당 피보나치 수들의 로그(lg) 값과 소인수들 구하기

피보나치 수의 범위가 크지 않으므로 math에 내장된 log2 함수를 사용해도 무방합니다.

 

문제는 소인수분해인데, 이 범위 안에 들어가는 마지막 피보나치 수가 \( 7.5 \times 10^{18} \) 정도의 큰 수입니다.

이러한 큰 수는 대표적으로 밀러-라빈 소수판별법 과 폴라드 로 알고리즘 을 사용하면 소인수분해할 수 있습니다. 다만 런타임 이후에 구할 시 메모리 초과(MLE)를 받을 수 있으니 이 경우에는 이 방식으로 구한 소인수들의 배열을 런타임 이전에 전처리해주면 쉽게 풀 수 있습니다.

 

큰 수의 소인수분해는 이 문제 (4149번: 큰 수 소인수분해) 에서 더 자세히 풀어볼 수 있습니다.

 

 

해당 요소들을 잘 조합했다면 출력 형식대로 출력해주면 됩니다.

 

---

코드

import sys, math
input = sys.stdin.readline

# fibo = [0, 1, 1, 2, 3, 5, 8, ..., 12200160415121876738]
# logs = [(None if num == 0 else math.log2(num)) for num in fibo]
# primes = [None, None, None, [2], [3], [5], [2, 2, 2], ..., [2, 557, 2417, 4531100550901]]


if __name__ == "__main__":
    while True:
        try:
            sp = input().split()
            left, right = int(sp[0], 16), int(sp[1], 16)
            if left >= right:
                raise Exception

            print(f'Range {left} to {right}:')
            exist = False

            for i in range(len(fibo)):
                if left <= fibo[i] <= right:
                    if fibo[i] == 0:
                        print("Fib(0) = 0, lg does not exist\nNo prime factors")
                    else:
                        print(f"Fib({i}) = {fibo[i]}, lg is {logs[i]:.6f}")
                        if fibo[i] == 1:
                            print("No prime factors")
                        else:
                            print(f"Prime factors: ", end='')
                            print(*primes[i])
                    exist = True

                if fibo[i] > right:
                    break

            if not exist:
                print("No Fibonacci numbers in the range")

            print()

        except Exception:
            break

---

난이도

2022년 1월 15일 기준 4463번의 난이도는 플래티넘 3입니다.

피보나치 수가 많지 않고, (어떻게든 구한) 소인수들을 전처리할 수 있다는 점에서 순수히 소인수분해를 런타임 중에 수행해야 하는 4149번과는 난이도 차이가 있는 편입니다.