Fibonacci

#include    <stdio.h>
#include    <stdlib.h>

void mult_matrice(long long a[][2],long long b[][2],long long c[][2])
{
    int i,j,k;
    for (i=0;i<2;++i)
        for (j=0;j<2;++j){
            c[i][j]=0;
            for (k=0;k<2;++k)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]);
        }
}

void set ( long long mat[][2],int k )
{
    mat[0][0]=mat[0][1]=mat[1][0]=mat[1][1]=k;
}

void copy( long long dest[][2],long long src[][2])
{
    int i,j;
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            dest[i][j]=src[i][j];
}

void fibonacci(int n,long long f[][2],long long sol[][2])
{
    long long aux[2][2];
    set(sol,0);
    sol[0][0]=sol[1][1]=1;

    while (n){
        if (n&1){
            set(aux,0);
            mult_matrice(sol,f,aux);
            copy(sol,aux);
        }
        set(aux,0);
        mult_matrice(f,f,aux);
        copy(f,aux);
        n>>=1;
    }

}

int main ()
{
    long long f[2][2],sol[2][2];
    int i,j,n;
    scanf("%d",&n);
    for (i=0;i<2;++i)
        for (j=0;j<2;++j)
            f[i][j]=i||j;

    fibonacci(n-1,f,sol);
    printf("%lld\n",sol[1][1]);
    return EXIT_SUCCESS;
}