Soluție HackerRank pentru Fibonacci Finding (easy), subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: Fibonacci Finding (easy)
- Domeniu: Number Theory
- Limbaj: Python 3
Challenge: Fibonacci Finding (easy)
Subdomeniu: Number Theory (number-theory)
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464725415
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/fibonacci-finding-easy/problem
Cerință
You're given three numbers: A, B, and N, and all you have to do is to find the number F_N where
F_0=A
F_1=B
F_i=F_i-1+F_i-2 ~for ~i ≥ 2
As the number can be very large, output it modulo 10^9+7.
Consider the following link: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
Input Format
First line contains a single integer T - the number of tests.
T lines follow, each containing three integers: A, B and N.
Output Format
For each test case output a single integer - F_N.
Constraints
1 ≤ T ≤ 1000
1 ≤ A,B,N ≤ 10^9
Cod sursă
#!/bin/python3
import os
import sys
import math
# Complete the solve function below.
def matrixMult(A,B):
tMod=10**9+7
C=[[(A[0][0]*B[0][0]+A[0][1]*B[1][0])%tMod,(A[0][0]*B[0][1]+A[0][1]*B[1][1])%tMod],[ (A[1][0]*B[0][0]+A[1][1]*B[1][0])%tMod,(A[1][0]*B[0][1]+A[1][1]*B[1][1])%tMod]]
return C
def matrixPower(A, exp):
if exp == 1:return A
Acop=A.copy()
if exp % 2 == 0:
A = matrixPower(A, exp // 2)
return matrixMult(A, A)
else:
A = matrixPower(A, exp - 1)
return matrixMult(A, Acop)
def solve(a, b, n):
if n==0:
return a
elif n==1:
return b
AMat=[[1,1],[1,0]]
BMat=matrixPower(AMat,n-1)
return (BMat[0][0]*b+BMat[0][1]*a)%(10**9+7)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
abn = input().split()
a = int(abn[0])
b = int(abn[1])
n = int(abn[2])
result = solve(a, b, n)
fptr.write(str(result) + '\n')
fptr.close()