Fastest Way to calculate Nth fibonacci number modulo M

general
, , , , , ,
21

Hello frendz …

code is updated and syncronized so that you can get AC on spoj with it … it is able to answer 61100 test cases on a rough idea. We can do some optimisation and can take it to 62000 easily . suggest some optimisation … i have one in my mind …

22

@i_am_what_i_am
you can try it now …

23

Hey guys i have applied the optimisation and boom i am able to take it to 63450 from 61100 . Think of some more optimisations .

@i_am_what_i_am
he was actually correct that this is not the fastest code for generating the answer but this may be the simplest code .

1 Like
24

could anyone explain what is the logic behind the function long long int f(long long int n, int depth=0) and
long long int mulmod(long long int a, long long int b) . Thankyou in advance.

25 
https://www.codechef.com/problems/CURR3
#include
using namespace std;
#define ll long long 
#define m 1000000007
void multiply(ll f[][2],ll g[][2])
{
    ll a=(f[0][0]*g[0][0]+f[0][1]*g[1][0])%m;
    ll b=(f[0][0]*g[0][1]+f[0][1]*g[1][1])%m;
    ll c=(f[1][0]*g[0][0]+f[1][1]*g[1][0])%m;
    ll d=(f[1][0]*g[0][1]+f[1][1]*g[1][1])%m;
    
    f[0][0]=a;
    f[0][1]=b;
    f[1][0]=c;
    f[1][1]=d;
}
void power(ll f[2][2],ll n)
{
    ll g[2][2]={{1,1},{1,0}};
    if(n==0||n==1)
    return;
    power(f,n/2);
    multiply(f,f);
    
    if(n%2==1)
    multiply(f,g);
}
ll fib(ll n)
{
    ll f[2][2]={{1,1},{1,0}};
    if(n==0)
    return 0;
    power(f,n-1);
    return f[0][0]%m;
}
 
int main() {
	ll n;
	cin>>n;
        cout<<fib(n)%m;
}