Discussion @ 1462. Uncle Scrooge's Gold @ Timus Online Judge

exwRabbits_AlMag(VNTU) How to make it fast? Is my formula correct? [2] // Problem 1462. Uncle Scrooge's Gold 23 Aug 2006 19:59

I use Fib(n-1)+Fib(n+1).
I can find Fib(n) in O(log n).
But the long arithmetics makes my programm too slow.
Help, please.

morbidel Re: How to make it fast? Is my formula correct? [1] // Problem 1462. Uncle Scrooge's Gold 30 Aug 2006 16:52

Read below some solutions. Your formula is correct, I used it too and recursevly computed the F[n]. I used long arithmetics in base 1.000.000 and it runs quick enough.

Denis Koshman Re: How to make it fast? Is my formula correct? // Problem 1462. Uncle Scrooge's Gold 12 Aug 2008 05:33

Better use long arithmetics base 2^P, and then fetch decimal answer by sequential divisions by 1'000'000 or something like that.

Discussion of Problem 1462. Uncle Scrooge's Gold