시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 2 40.000%

문제

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

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

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+XHJcblxyXG48cD4wXHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yzc3NFx1YzljMFx1YjljYywgMFx1Yzc1OCBcdWI4NWNcdWFkZjhcdWIyOTQgXHVjODE1XHVjNzU4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCAwXHVhY2ZjIDFcdWM3NDAgXHVjMThjXHVjNzc4XHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YjQ1MCBcdWM4MTVcdWMyMTggbG9cdWM2NDAgaGlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHViMjk0IDE2XHVjOWM0XHVjMjE4IFx1ZDQ1Y1x1ZDYwNCAoMHgxYVx1YjI5NCAyNilcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCA2NFx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1Yzc3NFx1YmE3MCwgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YjA1ZChFT0YpXHVjNzc0XHViMDk4IGxvICZnZTsgaGlcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWMwMSBcdWFkNmNcdWFjMDRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1XHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVhZDZjXHVhYzA0XHVjNzQwIFx1YmU0OCBcdWM5MDRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxMVx1Yzc3NCAyXHVjNzc4IFx1Yjg1Y1x1YWRmOChsZylcdWIyOTQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzVlY1x1YzEyZlx1YzlmOCBcdWM3OTBcdWI5YWMgXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVjMThjXHVjNzc4XHVjMjE4XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDQ2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlY29tcG9zaW5nIEZpYm9uYWNjaSBOdW1iZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5Tb21lIEZpYm9uYWNjaSBudW1iZXJzIGFyZSBpbW11bmUgdG8gem9tYmllIGF0dGFjayAmbWRhc2g7IGFzIHByaW1lIG51bWJlcnMgdGhleSBjYW4mcnNxdW87dCBiZSBkZWNvbXBvc2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaWJvbmFjY2kgbnVtYmVycyBhcmUgZGVmaW5lZCBieSB0aGUgZm9sbG93aW5nIHJlY3VycmVuY2U6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmlib25hY2NpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk0cHg7IHdpZHRoOjI4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGFuIGluZGVmaW5pdGUgbnVtYmVyIG9mIGludGVnZXIgcmFuZ2VzIG9mIG51bWJlcnMgdGhhdCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgNjQtYml0IHNpZ25lZCBpbnRlZ2Vycy4gWW91ciBqb2IgaXMgdG8gcmVwb3J0IGluIGluY3JlYXNpbmcgb3JkZXIgdGhlIEZpYm9uYWNjaSBudW1iZXJzIHRoYXQgZmFsbCB3aXRoaW4gdGhhdCByYW5nZSwgYXMgd2VsbCBhcyB0aGVpciBiYXNlLTIgbG9nYXJpdGhtIGFuZCB0aGVpciBwcmltZSBkZWNvbXBvc2l0aW9uICZtZGFzaDsgdGhlIHByaW1lIG51bWJlcnMgaW4gaW5jcmVhc2luZyBvcmRlciB3aGljaCwgd2hlbiBtdWx0aXBsaWVkIHRvZ2V0aGVyLCBnaXZlIHRoZSB2YWx1ZSBvZiB0aGUgRmlib25hY2NpIG51bWJlci4gSWYgdGhlcmUgaXMgbm8gRmlib25hY2NpIG51bWJlciBpbiB0aGUgcmFuZ2UsIHJlcG9ydCB0aGF0IGZhY3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgcmVtaW5kZXI6IHRoZSBsb2dhcml0aG0gb2YgemVybyBpcyB1bmRlZmluZWQsIGV2ZW4gdGhvdWdoIHplcm8gaXMgdGhlIGZpcnN0IEZpYm9uYWNjaSBudW1iZXIuIEFsc28gbm90ZSB0aGF0LCBieSBkZWZpbml0aW9uLCAwIGFuZCAxIGhhdmUgbm8gcHJpbWUgZmFjdG9ycywgZXZlbiB0aG91Z2ggdGhleSBhcmUgRmlib25hY2NpIG51bWJlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBhbiBpbmRldGVybWluYXRlIG51bWJlciBvZiBsaW5lcyBjb25zaXN0aW5nIG9mIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgKGxvIGFuZCBoaSkgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZSwgZ2l2ZW4gaW4gaGV4YWRlY2ltYWwgZm9ybWF0IChhcyBpbiAweDFhIG1lYW5pbmcgMjYgaW4gZGVjaW1hbCkuIEVhY2ggaW50ZWdlciBpcyBndWFyYW50ZWVkIHRvIGZpdCB3aXRoaW4gYSA2NC1iaXQgc2lnbmVkIGludGVnZXIuIFRoZSBwcm9ncmFtIHRlcm1pbmF0ZXMgd2hlbiBpdCBlaXRoZXIgZW5jb3VudGVycyBhbiBlbmQtb2YtZmlsZSBjb25kaXRpb24gb3Igd2hlbiBsbyAmZ2U7IGhpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHJhbmdlIGluIHRoZSBpbnB1dCBmaWxlLCBwcmludCB0aGUgcmFuZ2UgYW5kIHRoZSBGaWJvbmFjY2kgbnVtYmVyIGluZm9ybWF0aW9uIGFzIHNob3duIGluIHRoZSBzYW1wbGUgb3V0cHV0LCB3aXRoIGVhY2ggcmFuZ2Ugc2VwYXJhdGVkIGJ5IGEgYmxhbmsgbGluZS4gTm90ZSB0aGF0IHRoZSBiYXNlLTIgbG9nYXJpdGhtIChsZykgaXMgcmVwb3J0ZWQgd2l0aCBzaXggZGlnaXRzIHRvIHRoZSByaWdodCBvZiB0aGUgZGVjaW1hbCBwb2ludCwgYW5kIHRoYXQgdGhlIHByaW1lIGZhY3RvcnMgYXJlIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==