Related to ith Fibonacci number where i<=10^9

general
,
1

Can someone tell me how to solve this ?
We have an array of n elements where 1<=n<=10^5 and 1<=A[i]<=10^9 …

F(i) is ith fibonacci number

There will be q queries 1<=q<=10^5 Query is defined as:- 2 numbers l and r where 1<=l,r<=n

We have to find GCD( F(A[l]) , F(A[l+1]) … F(A[r]) )%10^9+7 where GCD of range of numbers is Greatest Common Divisor of all numbers

2

we can write GCD(F(a1),F(a2),…F(an)) as F(GCD(a1,a2,a3…an))

So for every query you need to find GCD(al,al+1,al+2…ar) efficiently and this can be done by using segment tree or sparse table.

UPD:

This might be helpful

1 Like
3

I don’t have link to that question… :frowning:

4

do you understand my answer?

5

Can we write GCD(F(a),F(b)) as F(GCD(a,b)) ?

6

we can answer query in logarithmic time using any standard data structure for range queries but the thing is getting i th fiboncci number as i can be as big as 10^9… we should be able to calculate nth fibonacci number quickly.To do that we can use Matrix Exponentiation

alt text

just look at the above matrix where n th fibonacci number is corresponding entry in right side matrix.
let’s indicate alt text. according to identity alt text

so we are almost done we need to calculate Q^n-1 and take the first element of first line…

but how do we compute Q^n-1 here comes the Matrix Exponentiation

alt text

the above pic says it all…To calculate M^n we need to calculate M^n/2 and multiply it by itself and so on…it is very obvious that tree height is log n

7

I appreciate your logic and even I submitted with same logic but no avail of it . Because ith fibonacci number where i<=10^9 is itself very large and can’t fit even in long long integer in C++ . There will be overflow …

8

isn’t there any kind of modulo like 10^9+7…

9

yes we can

10

yes it it … But if we dare to take modulo while finding Fibonacci number then it would directly inflict to GCD step which is last step …

11

Thanks ! it worked … :slight_smile:

12

anytime bro!

13

It is a question from an ongoing contest in hacker earth.

Please raise such questions once contest is over.

14

if it as a question from a live contest can u please provide the link to that contest @utkalsinha

15

Its a question from samsung research institute, banglore’s hiring challenge currently being held on hackerearth . Somebody remove this blog from discussion forum.

16

Sorry everyone ! I gave this contest a day before yesterday… I couldn’t solve it . So I asked it … I don’t have any other intention behind it

17

Questions like these kill the fairness of the contests. A lot of time is spent in making a problem and these discussions throw open all the ideas behind it!

I don’t understand why people cannot wait for the contest to get over!