Cod sursa(job #3136364)

Utilizator gal1l30Cristea Darius-Luca gal1l30 Data 6 iunie 2023 00:24:33
Problema Al k-lea termen Fibonacci Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>

typedef long long int ll;

void matrixMultiply(ll A[2][2], ll B[2][2], ll result[2][2], ll modulo) {
    ll temp[2][2];
    int i, j, k;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            temp[i][j] = 0;
            for (k = 0; k < 2; k++) {
                temp[i][j] += (A[i][k] * B[k][j]) % modulo;
                temp[i][j] %= modulo;
            }
        }
    }

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            result[i][j] = temp[i][j];
        }
    }
}

void matrixPower(ll A[2][2], ll exponent, ll modulo) {
    ll result[2][2] = {{1, 0}, {0, 1}};
    ll base[2][2];
    int i, j, k;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            base[i][j] = A[i][j];
        }
    }

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            matrixMultiply(result, base, result, modulo);
        }

        matrixMultiply(base, base, base, modulo);
        exponent /= 2;
    }

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            A[i][j] = result[i][j];
        }
    }
}

ll getFibonacciModulo(ll k, ll modulo) {
    if (k <= 1)
        return k;

    ll fibMatrix[2][2] = {{1, 1}, {1, 0}};
    matrixPower(fibMatrix, k - 1, modulo);

    return fibMatrix[0][0];
}

int main() {
    ll k;
    freopen("input.txt", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%lld", &k);

    ll result = getFibonacciModulo(k, 666013);

    printf("%lld\n", result);

    return 0;
}