시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB183463330.841%

문제

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

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

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

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

입력

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

출력

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

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

예제 입력 1

0x0 0x8
0x9 0xc
0x9 0x40
0x0 0x0

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjQ0NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IFx1YmQ4NFx1YzExZCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViNWE0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgXHVjODgwXHViZTQ0XHVjNzU4IFx1YWNmNVx1YWNhOVx1YzVkMCBcdWJhNzRcdWM1ZWRcdWMxMzFcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YzE4Y1x1YzIxOFx1YjI5NCBcdWJkODRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmlib25hY2NpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk0cHg7IHdpZHRoOjI4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjY0XHViZTQ0XHVkMmI4IFx1YmQ4MFx1ZDYzOFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhZGY4IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWNjM2VcdWM3NDAgXHViMmU0XHVjNzRjLCBcdWFkZjggXHVjMjE4XHVjNzU4IFx1YmMxMVx1Yzc3NCAyXHVjNzc4IFx1Yjg1Y1x1YWRmOFx1Yjk3YyBcdWNkZThcdWQ1NWMgXHVhYzEyXHVhY2ZjIFx1YzE4Y1x1Yzc3OFx1YzIxOCBcdWJkODRcdWQ1NzRcdWI5N2MgXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YjI5NCBcdWM2MjRcdWI5ODQgXHVjYzI4XHVjMjFjXHVjNzc0XHViYTcwLCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWMyMThcdWIyOTQgXHVhZGY4XHViOWNjXHVkMDdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhZGY4IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4wXHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yzc3NFx1YzljMFx1YjljYywgMFx1Yzc1OCBcdWI4NWNcdWFkZjhcdWIyOTQgXHVjODE1XHVjNzU4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCAwXHVhY2ZjIDFcdWM3NDAgXHVjMThjXHVjNzc4XHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCZuYnNwO1x1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHViNDUwIFx1YzgxNVx1YzIxOCBsb1x1YzY0MCBoaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWIyOTQgMTZcdWM5YzRcdWMyMTggXHVkNDVjXHVkNjA0ICgweDFhXHViMjk0IDI2KVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIDY0XHViZTQ0XHVkMmI4IFx1YmQ4MFx1ZDYzOFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMTggXHViYzk0XHVjNzA0XHVjNzc0XHViYTcwLCBcdWQzMGNcdWM3N2NcdWM3NTggXHViMDVkKEVPRilcdWM3NzRcdWIwOTggbG8gJmdlOyBoaVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzAxIFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViMmU0XHVjNzRjIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWFjZmMgXHVhYzE5XHVjNzc0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWFjMDRcdWM3NDAgXHViZTQ4IFx1YzkwNFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzExXHVjNzc0IDJcdWM3NzggXHViODVjXHVhZGY4KGxnKVx1YjI5NCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjNWVjXHVjMTJmXHVjOWY4IFx1Yzc5MFx1YjlhYyBcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWMxOGNcdWM3NzhcdWMyMThcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0NDYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVjb21wb3NpbmcgRmlib25hY2NpIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlNvbWUgRmlib25hY2NpIG51bWJlcnMgYXJlIGltbXVuZSB0byB6b21iaWUgYXR0YWNrICZtZGFzaDsgYXMgcHJpbWUgbnVtYmVycyB0aGV5IGNhbiZyc3F1bzt0IGJlIGRlY29tcG9zZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpYm9uYWNjaSBudW1iZXJzIGFyZSBkZWZpbmVkIGJ5IHRoZSBmb2xsb3dpbmcgcmVjdXJyZW5jZTombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9maWJvbmFjY2kucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6MjgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gYW4gaW5kZWZpbml0ZSBudW1iZXIgb2YgaW50ZWdlciByYW5nZXMgb2YgbnVtYmVycyB0aGF0IGNhbiBiZSByZXByZXNlbnRlZCBhcyA2NC1iaXQgc2lnbmVkIGludGVnZXJzLiBZb3VyIGpvYiBpcyB0byByZXBvcnQgaW4gaW5jcmVhc2luZyBvcmRlciB0aGUgRmlib25hY2NpIG51bWJlcnMgdGhhdCBmYWxsIHdpdGhpbiB0aGF0IHJhbmdlLCBhcyB3ZWxsIGFzIHRoZWlyIGJhc2UtMiBsb2dhcml0aG0gYW5kIHRoZWlyIHByaW1lIGRlY29tcG9zaXRpb24gJm1kYXNoOyB0aGUgcHJpbWUgbnVtYmVycyBpbiBpbmNyZWFzaW5nIG9yZGVyIHdoaWNoLCB3aGVuIG11bHRpcGxpZWQgdG9nZXRoZXIsIGdpdmUgdGhlIHZhbHVlIG9mIHRoZSBGaWJvbmFjY2kgbnVtYmVyLiBJZiB0aGVyZSBpcyBubyBGaWJvbmFjY2kgbnVtYmVyIGluIHRoZSByYW5nZSwgcmVwb3J0IHRoYXQgZmFjdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSByZW1pbmRlcjogdGhlIGxvZ2FyaXRobSBvZiB6ZXJvIGlzIHVuZGVmaW5lZCwgZXZlbiB0aG91Z2ggemVybyBpcyB0aGUgZmlyc3QgRmlib25hY2NpIG51bWJlci4gQWxzbyBub3RlIHRoYXQsIGJ5IGRlZmluaXRpb24sIDAgYW5kIDEgaGF2ZSBubyBwcmltZSBmYWN0b3JzLCBldmVuIHRob3VnaCB0aGV5IGFyZSBGaWJvbmFjY2kgbnVtYmVycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIGFuIGluZGV0ZXJtaW5hdGUgbnVtYmVyIG9mIGxpbmVzIGNvbnNpc3Rpbmcgb2YgdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyAobG8gYW5kIGhpKSBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLCBnaXZlbiBpbiBoZXhhZGVjaW1hbCBmb3JtYXQgKGFzIGluIDB4MWEgbWVhbmluZyAyNiBpbiBkZWNpbWFsKS4gRWFjaCBpbnRlZ2VyIGlzIGd1YXJhbnRlZWQgdG8gZml0IHdpdGhpbiBhIDY0LWJpdCBzaWduZWQgaW50ZWdlci4gVGhlIHByb2dyYW0gdGVybWluYXRlcyB3aGVuIGl0IGVpdGhlciBlbmNvdW50ZXJzIGFuIGVuZC1vZi1maWxlIGNvbmRpdGlvbiBvciB3aGVuIGxvICZnZTsgaGkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcmFuZ2UgaW4gdGhlIGlucHV0IGZpbGUsIHByaW50IHRoZSByYW5nZSBhbmQgdGhlIEZpYm9uYWNjaSBudW1iZXIgaW5mb3JtYXRpb24gYXMgc2hvd24gaW4gdGhlIHNhbXBsZSBvdXRwdXQsIHdpdGggZWFjaCByYW5nZSBzZXBhcmF0ZWQgYnkgYSBibGFuayBsaW5lLiBOb3RlIHRoYXQgdGhlIGJhc2UtMiBsb2dhcml0aG0gKGxnKSBpcyByZXBvcnRlZCB3aXRoIHNpeCBkaWdpdHMgdG8gdGhlIHJpZ2h0IG9mIHRoZSBkZWNpbWFsIHBvaW50LCBhbmQgdGhhdCB0aGUgcHJpbWUgZmFjdG9ycyBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==