Cod sursa(job #3154818)

Utilizator alexandrubilaBila Alexandru-Mihai alexandrubila Data 6 octombrie 2023 13:14:28
Problema Al k-lea termen Fibonacci Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>

using namespace std;

const int MOD = 666013;

ifstream f("kfib.in");
ofstream g("kfib.out");

int M[3][3] = { {0, 0, 0}, {0, 1, 1}, {0, 1, 0} };
int n; ///power
void copyMat(int A[][3], int B[][3])
{
    for(int i = 1 ; i <= 2 ; i++)
        for(int j = 1 ; j <= 2 ; j++)
            A[i][j] = B[i][j];
}

void multiply(int A[][3], int B[][3])
{
    int C[3][3];
    ///C = A * B;
    ///A = C;
    for(int i = 1 ; i <= 2 ; i++)
        for(int j = 1 ; j <= 2 ; j++)
        {
            C[i][j] = 0;
            for(int k = 1 ; k <= 2 ; k++)
                C[i][j] += (1LL * A[i][k] * B[k][j]) % MOD;
        }
    copyMat(A, C);
}

int expMat(int A[][3])
{
    int R[3][3]; //result
    copyMat(R, M);
    while(n)
    {
        if(n & 1)
            multiply(R, M);
        multiply(M, M);
        n >>= 1;
    }
    return R[1][1];
}

int main()
{
    ///int n;
    f >> n;
    if(n == 0)
        g << 0;
    else
        if(n == 1)
            g << 1;
        else
        {
            n -= 2;
            g << expMat(M);
        }
    return 0;
}