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

<syntaxhighlight lang="python" line>

1. 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()

</syntaxhighlight>