HackerRank Number Theory – Fibonacci Finding (easy)

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

Cerinta

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 \geq 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 \le T \le 1000$  
$1 \le A,B,N \le 10^9$

Cod sursa

#!/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()