3344 - Fibonacci2

Cerința

Șirul lui Fibonacci este definit astfel:

Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. 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

Exemplul 1

Intrare

6

Ieșire

8

Exemplul 2

Intrare

10

Ieșire

55

Rezolvare

#3344 - Fibonacci2
def fibonacci_modulo_n(n):
    fib = [0, 1]

    for i in range(2, n + 1):
        fib_i = (fib[i - 1] + fib[i - 2]) % 666013
        fib.append(fib_i)

    return fib[n]

def verificare_restrictii(n):    
    if 1 <= n <= 2.000.000.000:    
        return True
    else:
        return False

if __name__ == "__main__":
    n = int(input("Introduceți numărul n: "))
    
    result = fibonacci_modulo_n(n)
    
    print(f"Al {n}-lea termen al șirului Fibonacci modulo 666013 este: {result}")

Explicatie

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