Editing 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
<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):
    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>