Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | kfib.in, kfib.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Al k-lea termen Fibonacci
Se da sirul lui Fibonacci, F1 = 1, F2 = 1, ... Fi = Fi - 1 + Fi - 2. Sa se calculeze al N-lea termen al sirului modulo 666013.
Date de intrare
Fişierul de intrare kfib.in se gaseste un numar natural N.
Date de ieşire
În fişierul de ieşire kfib.out se va afisa al N-lea termen al sirului modulo 666013.
Restricţii
- 3 ≤ N ≤ 2.000.000.000
Exemplu
| kfib.in | kfib.out |
|---|---|
| 5 | 5 |
| 6 | 8 |
Indicatii pentru rezolvare
O implementare directa a relatiei de recurenta ar trebui sa obtina 20 de puncte si se gaseste aici.
Pentru a obtine 100 de puncte trebuie gasita o metoda mai eficienta de a rezolva aceasta recurenta, lucru realizabil prin transpunerea ei in matrici in felul urmator:
![\emph{}
\[ \left( \begin{array}{ccc}
a & b \\
1 & 0 \end{array} \right)\]](http://www.infoarena.ro/static/images/latex/b73d4375d66e74a5bba428dda063fa24_10.50012pt.gif "\emph{}
\[ \left( \begin{array}{ccc}
a & b \\
1 & 0 \end{array} \right)\]")
Nu imi merge sa fac matricile in latex, imi da eroarea asta:" Warning: Cannot modify header information - headers already sent by (output started at /home/infoarena/live/www/views/header.php:98) in /home/infoarena/live/common/log.php on line 309 "
bogdan2412: Ramasesem fara spatiu pe disc iara :P
