We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Fibonacci LCM
  5. Discussions

Fibonacci LCM

Sort by

recency

|

8 Discussions

|

  • tordjarv
     + 0 comments

    A few tips (no code) that helped me: 1) F_k devides F_l iff k devides l 2) gcd(F_k, F_l) = F_gcd(k,l) 3) Use that F_k = 1/2^k ( (1+1/sqrt(5))(1+sqrt(5))^(k-1) +(1-1/sqrt(5))(1-sqrt(5))^(k-1)) 4) Use Fermats little theorem i.e. a^p is congurent to a mod p if p is a prime to compute the multiplicative inverse of a mod p ( inv(a) = a^(p-2) mod p) 5) lcm(lcm(a_1,a_2,...,a_k),a_(k+1)) = (lcm(a_1,a_2,...,a_k) a_(k+1))/lcm(gcd(a_1,a_(k+1)),gcd(a_2,a_(k+1)),...,gcd(a_k,a_(k+1))

  • TChalla
     + 0 comments

    Python 3 solution

    from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 9)

p = 10 ** 9 + 7

def matrix_mul(A, B, p = 10 ** 9 + 7):
    '''
    multiply two 2x2 matrices mod p
    '''
    return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p ,
            (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p],
            [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p,
            (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p]]

def matrix_pow(A, n, p = 10 ** 9 + 7):
    '''
    calculate A^n mod p for a 2x2 matrix
    '''
    if n == 0:
        return [[1, 0], [0, 1]]
    B = matrix_pow(A, n // 2, p)
    B = matrix_mul(B, B, p)
    if n % 2 == 1:
        B = matrix_mul(B, A, p)
    return B

def fibonacci(A, B, n, p = 10 ** 9 + 7):
    '''
    Given that F[0]=A, F[1]=B and F[i]=F[i-1]+F[i-2], find F[n]%p
    '''
    M = matrix_pow([[1, 1], [1, 0]], n, p)
    return (M[1][0] * B + M[1][1] * A) % p

def fib_lcm(A):
    if len(A) == 1:
        return fibonacci(0, 1, A[0])
    B = list(set([gcd(A[0], a) for a in A[1:]]))
    return (fib_lcm(A[1:]) * fibonacci(0, 1, A[0]) * pow(fib_lcm(B), p - 2, p)) % p

N = int(input())
A = [int(input()) for _ in range(N)]
print(fib_lcm(A))

  • OKEZINO
     + 1 comment

    KOTLIN

    Only one Test passed, can someone help with a good explainatory sudo code solution to this problem?

    my code though

    fun solve(f: Array<Int>): Int {
        var stack = mutableListOf<Int>()
        fun fibonacci(b : Int) : Int{
            return if(b == 0) 0 else if(b == 1) 1
            else fibonacci(b - 1) + fibonacci(b -2)
        }
        fun gcd (a : Int,b: Int) : Int{
            if(a==0) return b else return gcd(b%a,a)
        }

        fun lcm(a:Int,b:Int):Int{
            return (a*b)/gcd(a,b)
        }
        f.forEach{
            stack.add(fibonacci(it))
        }
        var lcmResult =  stack[0]

        for(i in 1 until stack.size){
            lcmResult = lcm(lcmResult,stack[i])
        }

 

        return lcmResult
    }

  • tht2005
     + 0 comments

    just matrix mulplication :))

  • Strongbow
     + 0 comments

    The single example given is too trivial. The question require another with larger values so that the wrapped values from mod arithmetic are visible. This is where I was caught out and I feel cheated and the exercise was a waste of time. There is another general issue involving using mod arithmetic. Unless it is required for the Maths involved in the problem why create test cases whose outputs will overflow the native machine numerical limits? Why do this and then require mod arithmetic so that so wrapped nonsense value is required for the answer? I didnt think much of the editorial either.