Cod sursa(job #1112055)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 19 februarie 2014 13:05:31
Problema Al k-lea termen Fibonacci Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>
#define mod 666073
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int K, Z[3][3];

void inmultire(const int A[][3], const int B[][3], int C[][3])
{
    int aux[3][3];
    memset(aux, 0, sizeof(aux));
    for (int i=1; i<=2; ++i)
        for (int j=1; j<=2; ++j)
        {
            long long sum=0;
            for  (int k=1; k<=2; ++k)
                sum+=1LL*A[i][k]*B[k][j];
            aux[i][j]=(sum%mod);
        }
    memcpy(C, aux, sizeof(aux));
}

void log_pow(int Z[][3], int K)
{
    int res[3][3];
    memset(res, 0, sizeof(res));
    res[1][1]=res[2][2]=1;
    while (K)
    {
        if (K%2) inmultire(Z, res, res);
        inmultire(Z, Z, Z); K/=2;
    }
}

int main()
{
    f>>K;
    Z[0][0]=0; Z[0][1]=1;
    Z[1][0]=1; Z[1][1]=1;
    log_pow(Z, K-1);
    g<<Z[2][2]<<'\n';
    return 0;
}