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

Exemplu 1

Intrare

6

Ieșire

8

Exemplu 2

Intrare

10

Ieșire

55

Rezolvare

#3344 - Fibonacci2
def multiply(a, b, MOD):
    res = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] += (a[i][k] * b[k][j]) % MOD
                res[i][j] %= MOD
    return res

def power(matrix, exp, MOD):
    if exp == 1:
        return matrix
    if exp % 2 == 0:
        half_pow = power(matrix, exp // 2, MOD)
        return multiply(half_pow, half_pow, MOD)
    else:
        return multiply(matrix, power(matrix, exp - 1, MOD), MOD)

def fibonacci(n, MOD):
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = power(base_matrix, n - 1, MOD)
    return result_matrix[0][0] % MOD

def main():
    n = int(input("Introduceți n: "))
    MOD = 666013
    result = fibonacci(n, MOD)
    print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")

if __name__ == "__main__":
    main()