E. Фибоначийн тоо

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жонд бүх Фибоначийн тооны $10^13$-нд хуваасан үлдэгдлийн жагсаалт бий. Энэ жагсаалт $0$, $1$-ээс эхлэн хязгааргүй үргэлжлэнэ. Жагсаалт дахь тоо бүр (эхний хоёр тооноос бусад нь) өмнөх хоёр тооныхоо нийлбэрийн $10^13$-д хуваасан үлдэгдэл байж чадах нь мөн тодорхой билээ.

Жон $f$ ($0 ≤ f < 10^13$) тоог жагсаалтын хэддүгээрт анх олдохыг ихэд сонирхож байгаа бол түүнд тусалж хэрвээ энэ тоо жагсаалтад байгаа бол дугаарыг байхгүй бол байхгүй тухай мэдэгдэнэ үү.

Жагсаалтыг $0$-ээс эхлэн дугаарлажээ: $0$-р байранд $0$, $1$-р байранд $1$, $2$-р байранд $1$, $3$-р байранд $2$, $4$-р байранд $3$ гэх мэтчилэн. Өөрөөр хэлбэл эхнээс нь жагсааж бичвэл дараах байдлаар харагдах нь: $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21,$ ...

Оролт

Нэг мөрөнд $f$ ($0 ≤ f < 10^13$) тоо байна.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Өгөгдсөн тоо Жоны жагсаалтын хэддүгээрт анх олдохыг хэвлэнэ. Хэрвээ энэ тоо олдохооргүй бол $-1$ гэж хэвлэнэ үү.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
13
Гаралт
7
Оролт
377
Гаралт
14
Сэтгэгдлүүдийг ачааллаж байна...