시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 423 | 107 | 82 | 25.466% |
어떤 피보나치 수는 좀비의 공격에 면역성이 있다. 그 이유는 소수는 분해할 수 없기 때문이다.
피보나치 수는 아래와 같이 재귀적으로 정의할 수 있다.
64비트 부호있는 정수로 표현할 수 있는 정수 범위가 주어진다. 이때, 그 구간에 포함되는 피보나치 수를 찾은 다음, 그 수의 밑이 2인 로그를 취한 값과 소인수 분해를 하는 프로그램을 작성하시오. 소인수는 오름 차순이며, 여러 번 등장하는 수는 그만큼 출력해야 한다. 만약, 그 구간에 해당하는 피보나치 수가 없는 경우에는 없다고 출력하면 된다.
0은 첫 번째 피보나치 수이지만, 0의 로그는 정의되지 않는다. 또, 0과 1은 소인수가 없다.
첫째 줄에 구간을 나타내는 음이 아닌 두 정수 lo와 hi가 주어진다. 두 수는 16진수 표현 (0x1a는 26)으로 주어진다. 각 정수는 모두 64비트 부호있는 정수 범위이며, 파일의 끝(EOF)이나 lo ≥ hi인 경우에 종료한다.
입력으로 주어지는 각 구간에 대해서, 구간을 출력한 다음 예제 출력과 같이 피보나치 수에 대한 정보를 출력한다. 각 구간은 빈 줄로 나누어져 있어야 한다.
밑이 2인 로그(lg)는 소수점 여섯째 자리 까지 출력하며, 소인수는 공백으로 구분한다.
0x0 0x8 0x9 0xc 0x9 0x40 0x0 0x0
Range 0 to 8: Fib(0) = 0, lg does not exist No prime factors Fib(1) = 1, lg is 0.000000 No prime factors Fib(2) = 1, lg is 0.000000 No prime factors Fib(3) = 2, lg is 1.000000 Prime factors: 2 Fib(4) = 3, lg is 1.584963 Prime factors: 3 Fib(5) = 5, lg is 2.321928 Prime factors: 5 Fib(6) = 8, lg is 3.000000 Prime factors: 2 2 2 Range 9 to 12: No Fibonacci numbers in the range Range 9 to 64: Fib(7) = 13, lg is 3.700440 Prime factors: 13 Fib(8) = 21, lg is 4.392317 Prime factors: 3 7 Fib(9) = 34, lg is 5.087463 Prime factors: 2 17 Fib(10) = 55, lg is 5.781360 Prime factors: 5 11
ICPC > Regionals > North America > Pacific Northwest Regional > 2010 Pacific Northwest Region Programming Contest E번