Recently, I encountered a problem where this relation in GCD and Fibonacci Numbers came in very handy.

Problem is, given an array of size n of positive integers and two non-negative integers l and r (0 <= l <= r < n). And we need to calculate gcd(fib(l), ...., fib(r)) where fib(i) is the ith fibonacci number.

Here, the relation that is very useful is gcd(fib(m), fib(n)) = fib(gcd(m, n)).

A more detailed description can be found here: https://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

link to the problem plz.

Maybe this

thanks @rishabh0305

I think that you could precompute the fibonacci numbers into an array and then create a segment tree with gcd operation in this array.