Fibonacci meets GCD --- giving wrong ans & runtime error --- segment tree

#1

https://ide.codingblocks.com/s/71276
split fib array in 2 part and solve it O(N)
then apply gcd on nodes of segment tree

#2

Hi

In this question the trick is

GCD(F(a),F(b), F©) = F(GCD(a,b,c)) // can be proved mathematically give it a try to prove

This is coz if we built a segtree storing sum of F(a), F(b), F©…and so on , that will over flow,

as you can see A[i] is till 10^9 so we take store GCD and then in the end find the Fibonacci number.

https://ide.codingblocks.com/s/70960

Hit like if you get it Cheers!

#3

As you are not responding to thread i’m marking this as closed, if you still have doubt later on you can post in the same thread.

Hit like if you get it!
Cheers!

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.