Latest revision as of 17:05, 18 May 2024

Cerința[edit | edit source]

Ș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[edit | edit source]

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

Date de ieșire[edit | edit source]

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

Restricții și precizări[edit | edit source]

1 ≤ n ≤ 2.000.000.000

Exemplu:[edit | edit source]

Intrare

Ieșire

Explicație[edit | edit source]

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

Rezolvare[edit | edit source]

<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>

@@ Line 4: / Line 4: @@
 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 ==
-≤ n ≤ 2.000.000.000
-== Exemplu 1 ==
-; Intrare
-: 6
-; Ieșire
-: 8
-<br>
-== Exemplu 2 ==
-; Intrare
-: 10
-; Ieșire
-: 55
-<br>
-== Rezolvare ==
-<syntaxhighlight lang="python" line>
-#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):
+= Date de intrare =
-     if exp == 1:
+Programul citește de la tastatură numărul <code>n</code>.
-         return matrix
-     if exp % 2 == 0:
+= Date de ieșire =
-         half_pow = power(matrix, exp // 2, MOD)
+Programul va afișa pe ecran numărul <code>F</code>, reprezentând al <code>n</code>-lea termen al șirului, modulo <code>666013</code>.
-        return multiply(half_pow, half_pow, MOD)
+= Restricții și precizări =
+* <code>1 ≤ n ≤ 2.000.000.000</code>
+= Exemplu: =
+Intrare
+Ieșire
+=== Explicație ===
+Termenii sunt: <code>1 1 2 3 5 8 13 21 34 55 89 ...</code>
+:
+== 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:
-         return multiply(matrix, power(matrix, exp - 1, MOD), MOD)
+         print("Datele nu corespund restrictiilor impuse")
+        return False
-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: "))
+     n = int(input())
-     MOD = 666013
+     if verifica_restrictii(n):
-    result = fibonacci(n, MOD)
+        result = pwr(initMat, n)
-    print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")
+        print(result.mat[0][1])
 if __name__ == "__main__":
      main()
 </syntaxhighlight>