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.
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))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Fibonacci LCM
You are viewing a single comment's thread. Return to all 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))