Large Fibonacci Number (N can be upto 10^15000000) -SPOJ

ssrivastava990 · June 23, 2020, 7:07pm

Oh again I forgot , that we can find Fibo number in Logn complexity by using Matrix expo … I think i have to eat almonds ,

sarthak_eddy · June 25, 2020, 5:57am

If having trouble in writing solution refer to this link.

github.com

sarthakeddy/Spoj-solution/blob/master/hardFib.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll mod=998244353;
const int N=2e6+5;

ll a,b,c,d;
void fastDoublingfib(long long int n,long long int ans[])
{
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fastDoublingfib((n/2),ans);
    a = ans[0];
    b = ans[1];
    c = 2*b - a;

This file has been truncated. show original

ssrivastava990 · June 25, 2020, 6:02am

yeah u use matrix exponentiation right ?

sarthak_eddy · June 25, 2020, 6:02am

Fast doubling method.

ssrivastava990 · June 25, 2020, 6:03am

Both are different ?

sarthak_eddy · June 25, 2020, 6:05am

Yup they are.