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:

Intrare

6

Ieșire

8

Explicație

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

Rezolvare

<syntaxhighlight lang="python" line="1"> MOD = 666013

class Mat:

   def __init__(self, mat):
       self.mat = mat

nullMat = Mat([[1, 0], [0, 1]]) initMat = Mat([[1, 1], [1, 0]])

def prod(a, b):

   ret = Mat([[0, 0], [0, 0]])
   ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD
   ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD
   ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD
   ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD
   return ret

def pwr(mat, n):

   if n == 0:
       return nullMat
   if n % 2 == 1:
       return prod(mat, pwr(prod(mat, mat), n // 2))
   return pwr(prod(mat, mat), n // 2)

def verifica_restrictii(n):

   if 1 <= n <= 2000000000:
       return True
   else:
       print("Datele nu corespund restrictiilor impuse")
       return False

def main():

   n = int(input())
   if verifica_restrictii(n):
       result = pwr(initMat, n)
       print(result.mat[0][1])

if __name__ == "__main__":

   main()

</syntaxhighlight>