Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-10 09:24:18.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:kfib.in, kfib.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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.inkfib.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:

\[ \left( \begin{array}{cccc}F & F & -7 & 0 \\9 & 2 & -6 & 2 \\-4 & 1 & -4 & 1 \\-1 & 8 & 0 & -2 \end{array} \right)\]
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?