fibonacci-gcd.py

# Mathematics > Number Theory > Fibonacci GCD
# Find gcd for n fibonacci numbers.
#
# https://www.hackerrank.com/challenges/fibonacci-gcd/problem
# https://www.hackerrank.com/contests/infinitum9/challenges/fibonacci-gcd
# challenge id: 4503
#

from math import gcd


MOD = 1000000007


def multm(A, B):
    """ produit matriciel: A * B """
    a00, a10, a01, a11 = A
    b00, b10, b01, b11 = B
    return [(a00 * b00 + a10 * b01) % MOD, (a00 * b10 + a10 * b11) % MOD,
            (a01 * b00 + a11 * b01) % MOD, (a01 * b10 + a11 * b11) % MOD]


def multv(A, V):
    """ produit matrice/vecteur: A * V """
    a00, a10, a01, a11 = A
    b0, b1 = V
    return [(a00 * b0 + a10 * b1) % MOD,
            (a01 * b0 + a11 * b1) % MOD]


def power(M, k):
    """ fast exponentiation M^k """
    P = [1, 0,
         0, 1]

    if k == 0:
        return P
    if k == 1:
        return M

    while k != 0:
        if k % 2 == 1:
            P = multm(P, M)
        M = multm(M, M)
        k //= 2
    return P


# on utilise la propriété suivante:
# gcd(F(a), F(b)) = F(gcd(a, b))

# calcul du gcd(aᵢ)
g = 0
n = int(input())
for i in range(n):
    g = gcd(g, int(input()))

# calcul de F(g) (cf. https://www.hackerrank.com/challenges/fibonacci-finding-easy)
# http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
# Fn = A^n * F0
# avec Fn[f(n+1) f(n))
# et A = [[1 1][1 0]]
A = [1, 1, 1, 0]
An = power(A, g)
F0 = [1, 0]
Fn = multv(An, F0)
print(Fn[1])