3344 - Fibonacci2
De la Universitas MediaWiki
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
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()