시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+PFwvcD5cclxuXHJcbjxwPjY0XHViZTQ0XHVkMmI4IFx1YmQ4MFx1ZDYzOFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI5N2MgXHVjYzNlXHVjNzQwIFx1YjJlNFx1Yzc0YywgXHVhZGY4IFx1YzIxOFx1Yzc1OCBcdWJjMTFcdWM3NzQgMlx1Yzc3OCBcdWI4NWNcdWFkZjhcdWI5N2MgXHVjZGU4XHVkNTVjIFx1YWMxMlx1YWNmYyBcdWMxOGNcdWM3NzhcdWMyMTggXHViZDg0XHVkNTc0XHViOTdjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMxOGNcdWM3NzhcdWMyMThcdWIyOTQgXHVjNjI0XHViOTg0IFx1Y2MyOFx1YzIxY1x1Yzc3NFx1YmE3MCwgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMjE4XHViMjk0IFx1YWRmOFx1YjljY1x1ZDA3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MFx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NzRcdWM5YzBcdWI5Y2MsIDBcdWM3NTggXHViODVjXHVhZGY4XHViMjk0IFx1YzgxNVx1Yzc1OFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjYxMCwgMFx1YWNmYyAxXHVjNzQwIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWI0NTAgXHVjODE1XHVjMjE4IGxvXHVjNjQwIGhpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YjI5NCAxNlx1YzljNFx1YzIxOCBcdWQ0NWNcdWQ2MDQgKDB4MWFcdWIyOTQgMjYpXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgNjRcdWJlNDRcdWQyYjggXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOCBcdWJjOTRcdWM3MDRcdWM3NzRcdWJhNzAsIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWIwNWQoRU9GKVx1Yzc3NFx1YjA5OCBsbyAmZ2U7IGhpXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMDEgXHVhZDZjXHVhYzA0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWIyZTRcdWM3NGMgXHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YWQ2Y1x1YWMwNFx1Yzc0MCBcdWJlNDggXHVjOTA0XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMTFcdWM3NzQgMlx1Yzc3OCBcdWI4NWNcdWFkZjgobGcpXHViMjk0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1ZWNcdWMxMmZcdWM5ZjggXHVjNzkwXHViOWFjIFx1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzAsIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ0NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEZWNvbXBvc2luZyBGaWJvbmFjY2kgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBGaWJvbmFjY2kgbnVtYmVycyBhcmUgaW1tdW5lIHRvIHpvbWJpZSBhdHRhY2sgJm1kYXNoOyBhcyBwcmltZSBudW1iZXJzIHRoZXkgY2FuJnJzcXVvO3QgYmUgZGVjb21wb3NlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rmlib25hY2NpIG51bWJlcnMgYXJlIGRlZmluZWQgYnkgdGhlIGZvbGxvd2luZyByZWN1cnJlbmNlOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpYm9uYWNjaS5wbmdcIiBzdHlsZT1cImhlaWdodDo5NHB4OyB3aWR0aDoyODBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiBhbiBpbmRlZmluaXRlIG51bWJlciBvZiBpbnRlZ2VyIHJhbmdlcyBvZiBudW1iZXJzIHRoYXQgY2FuIGJlIHJlcHJlc2VudGVkIGFzIDY0LWJpdCBzaWduZWQgaW50ZWdlcnMuIFlvdXIgam9iIGlzIHRvIHJlcG9ydCBpbiBpbmNyZWFzaW5nIG9yZGVyIHRoZSBGaWJvbmFjY2kgbnVtYmVycyB0aGF0IGZhbGwgd2l0aGluIHRoYXQgcmFuZ2UsIGFzIHdlbGwgYXMgdGhlaXIgYmFzZS0yIGxvZ2FyaXRobSBhbmQgdGhlaXIgcHJpbWUgZGVjb21wb3NpdGlvbiAmbWRhc2g7IHRoZSBwcmltZSBudW1iZXJzIGluIGluY3JlYXNpbmcgb3JkZXIgd2hpY2gsIHdoZW4gbXVsdGlwbGllZCB0b2dldGhlciwgZ2l2ZSB0aGUgdmFsdWUgb2YgdGhlIEZpYm9uYWNjaSBudW1iZXIuIElmIHRoZXJlIGlzIG5vIEZpYm9uYWNjaSBudW1iZXIgaW4gdGhlIHJhbmdlLCByZXBvcnQgdGhhdCBmYWN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHJlbWluZGVyOiB0aGUgbG9nYXJpdGhtIG9mIHplcm8gaXMgdW5kZWZpbmVkLCBldmVuIHRob3VnaCB6ZXJvIGlzIHRoZSBmaXJzdCBGaWJvbmFjY2kgbnVtYmVyLiBBbHNvIG5vdGUgdGhhdCwgYnkgZGVmaW5pdGlvbiwgMCBhbmQgMSBoYXZlIG5vIHByaW1lIGZhY3RvcnMsIGV2ZW4gdGhvdWdoIHRoZXkgYXJlIEZpYm9uYWNjaSBudW1iZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29udGFpbnMgYW4gaW5kZXRlcm1pbmF0ZSBudW1iZXIgb2YgbGluZXMgY29uc2lzdGluZyBvZiB0d28gbm9uLW5lZ2F0aXZlIGludGVnZXJzIChsbyBhbmQgaGkpIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UsIGdpdmVuIGluIGhleGFkZWNpbWFsIGZvcm1hdCAoYXMgaW4gMHgxYSBtZWFuaW5nIDI2IGluIGRlY2ltYWwpLiBFYWNoIGludGVnZXIgaXMgZ3VhcmFudGVlZCB0byBmaXQgd2l0aGluIGEgNjQtYml0IHNpZ25lZCBpbnRlZ2VyLiBUaGUgcHJvZ3JhbSB0ZXJtaW5hdGVzIHdoZW4gaXQgZWl0aGVyIGVuY291bnRlcnMgYW4gZW5kLW9mLWZpbGUgY29uZGl0aW9uIG9yIHdoZW4gbG8gJmdlOyBoaS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCByYW5nZSBpbiB0aGUgaW5wdXQgZmlsZSwgcHJpbnQgdGhlIHJhbmdlIGFuZCB0aGUgRmlib25hY2NpIG51bWJlciBpbmZvcm1hdGlvbiBhcyBzaG93biBpbiB0aGUgc2FtcGxlIG91dHB1dCwgd2l0aCBlYWNoIHJhbmdlIHNlcGFyYXRlZCBieSBhIGJsYW5rIGxpbmUuIE5vdGUgdGhhdCB0aGUgYmFzZS0yIGxvZ2FyaXRobSAobGcpIGlzIHJlcG9ydGVkIHdpdGggc2l4IGRpZ2l0cyB0byB0aGUgcmlnaHQgb2YgdGhlIGRlY2ltYWwgcG9pbnQsIGFuZCB0aGF0IHRoZSBwcmltZSBmYWN0b3JzIGFyZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=