Cerința

Șirul lui Fibonacci este definit astfel:

$$ F_n = \begin{cases}
1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\
F_{n-1} + F_{n-2} & \text{dacă } n > 2.
\end{cases} $$

Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.

Restricții și precizări

1 ≤ n ≤ 2.000.000.000

Exemplu

Intrare

Ieșire

Explicație

Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Fibonacci2:

#include <iostream>

using namespace std;

typedef int MatFib[2][2];

const int MOD = 666013;

void Produs(MatFib A , MatFib B, MatFib P)
{
    P[0][0] = (1LL * A[0][0] * B[0][0] + 1LL * A[0][1] * B[1][0]) % MOD;
    P[0][1] = (1LL * A[0][0] * B[0][1] + 1LL * A[0][1] * B[1][1]) % MOD;
    P[1][0] = (1LL * A[1][0] * B[0][0] + 1LL * A[1][1] * B[1][0]) % MOD;
    P[1][1] = (1LL * A[1][0] * B[0][1] + 1LL * A[1][1] * B[1][1]) % MOD;
}

void Atrib(MatFib D ,MatFib S)
{
    D[0][0] = S[0][0];
    D[0][1] = S[0][1];
    D[1][0] = S[1][0];
    D[1][1] = S[1][1];
}

int Fibo(int n)
{
    MatFib A = {{1,1},{1,0}}, B , R = {{1,0},{0,1}};
    while(n > 0)
    {
        if(n % 2 == 1)
        {
            Produs(R , A, B);
            Atrib(R, B);
        }
        Produs(A, A, B);
        Atrib(A , B);
        n /= 2;
    }
    
    return R[0][1];
}

int main()
{
    int n;
    cin >> n;
    cout << Fibo(n);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3344 Fibonacci2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3344 Fibonacci2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3344 Fibonacci2