시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB269773554928.039%

문제

피보나치 수의 정의는 다음과 같다.

  • f1 := 1
  • f2 := 2
  • fn := fn-1 + fn-2 (n ≥ 3)

두 수 a와 b가 주어졌을 때, 구간 [a, b]에 포함되는 피보나치 수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (a ≤ b ≤ 10100) 두 수 a와 b는 불필요한 0으로 시작하지 않는다.

출력

각 테스트 케이스에 대해서, a ≤ fi ≤ b 인 피보나치 수 fi의 개수를 출력한다.

예제 입력 1

10 100
1234567890 9876543210
0 0

예제 출력 1

5
4
W3sicHJvYmxlbV9pZCI6IjY1NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWM3NThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mPHN1Yj4xPFwvc3ViPiA6PSAxPFwvbGk+XHJcblx0PGxpPmY8c3ViPjI8XC9zdWI+IDo9IDI8XC9saT5cclxuXHQ8bGk+ZjxzdWI+bjxcL3N1Yj4gOj0gZjxzdWI+bi0xPFwvc3ViPiArIGY8c3ViPm4tMjxcL3N1Yj4gKG4gJmdlOyAzKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMyMTggYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWQ2Y1x1YWMwNCBbYSwgYl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YjQ1MCBcdWM4MTVcdWMyMTggYVx1YzY0MCBiXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChhICZsZTsgYiAmbGU7IDEwPHN1cD4xMDA8XC9zdXA+KSBcdWI0NTAgXHVjMjE4IGFcdWM2NDAgYlx1YjI5NCBcdWJkODhcdWQ1NDRcdWM2OTRcdWQ1NWMgMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYSAmbGU7IGY8c3ViPmk8XC9zdWI+ICZsZTsgYiBcdWM3NzggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOCBmPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjY1NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb3cgbWFueSBGaWJzPyIsImRlc2NyaXB0aW9uIjoiPHA+UmVjYWxsIHRoZSBkZWZpbml0aW9uIG9mIHRoZSBGaWJvbmFjY2kgbnVtYmVyczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mPHN1Yj4xPFwvc3ViPiZuYnNwOzo9IDE8XC9saT5cclxuXHQ8bGk+ZjxzdWI+MjxcL3N1Yj4mbmJzcDs6PSAyPFwvbGk+XHJcblx0PGxpPmY8c3ViPm48XC9zdWI+Jm5ic3A7Oj0gZjxzdWI+bi0xPFwvc3ViPiZuYnNwOysgZjxzdWI+bi0yPFwvc3ViPiZuYnNwOyhuICZnZTsgMyk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5HaXZlbiB0d28gbnVtYmVycyBhIGFuZCBiLCBjYWxjdWxhdGUgaG93IG1hbnkgRmlib25hY2NpIG51bWJlcnMgYXJlIGluIHRoZSByYW5nZSBbYSxiXS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBub24tbmVnYXRpdmUgaW50ZWdlciBudW1iZXJzIGEgYW5kIGIuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYT1iPTAuIE90aGVyd2lzZSwgYSZsdDs9YiZsdDs9MTA8c3VwPjEwMDxcL3N1cD4uIFRoZSBudW1iZXJzIGEgYW5kIGIgYXJlIGdpdmVuIHdpdGggbm8gc3VwZXJmbHVvdXMgbGVhZGluZyB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIG51bWJlciBvZiBGaWJvbmFjY2kgbnVtYmVycyBmaSB3aXRoIGEmbHQ7PWZpJmx0Oz1iLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2000 F번