Cod sursa(job #380493)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 6 ianuarie 2010 12:30:44
Problema Al k-lea termen Fibonacci Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
int a,b,pp[3][3],A[3][3];
void prod(int X1[3][3],int X2[3][3])
{
    int X3[3][3];
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
        {
            X3[i][j]=0;
            for(int k=1;k<=2;++k)
                X3[i][j]=(X3[i][j]+(long long)((long long)(X1[i][k]%b)*(long long)(X2[k][j]%b))%b)%b;
        }
    for(int i=1; i<=2; ++i)
        for(int j=1; j<=2; ++j)
            X1[i][j]=X3[i][j];
}
void pz(int p)
{
    pp[1][1]=1; pp[1][2]=0; pp[2][1]=0; pp[2][2]=1;
    A[1][1]=1; A[2][1]=1; A[1][2]=1; A[2][2]=0;
    while(p)
    {
        if(p%2==1)
        {
            prod(pp,A); //pepe
            // PEPE PE, PE PEPE!
        }
        prod(A,A);
        p/=2;
    }
    int c[3][3]; 
    c[1][1]=1; c[1][2]=0; c[2][1]=0; c[2][2]=0;
    prod(pp,c);
    printf("%d",pp[2][1]);
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&a); b=666013;
    //RIFLEMEN, SHOOT FASTER!
    pz(a); //PEPE
    return 0;
}