matrix

#include <stdio.h>

// Работа с числами в кольце по модулю n:
void mod(int * val, int n); // Функция вычисляет значение val по модулю n
void inc(int * val, int n, int k); // Функция увеличивает значение val на k по модулю n
void dec(int * val, int n, int k); // Функция уменьшает значение val на k по модулю n

// Работа с матрицами:
void copy(int * A, int * B); // Копирует двумерную матрицу B в матрицу A
void print(int * A); // Выводит двумерную матрицу на экран
void prod(int * A, int * B, int * C, int n); // В матрицу C записывается результат умножения матрицы A на матрицу B по модулю n
void power(int * A, int k, int n); // Возводит матрицу A в степень k. Элементы матрицы вычисляются по модулю n

int main(){
//  Ввод начальных условий:
    int a, b, x1, x2, n, base;
    printf("X(n) = a*X(n-1)+b*X(n-2), X(n) (mod base)\n");
    printf("Enter a, b, X(1), X(2), n, base: ");
    scanf("%d %d %d %d %d %d", &a, &b, &x1, &x2, &n, &base);

//  Получение матрицы оператора:
    unsigned const int SIZE = 2; // Размерность матрицы
    int A[SIZE][SIZE]; // Матрица оператора
    A[0][0] = 0; A[0][1] = b;
    A[1][0] = 1; A[1][1] = a;

//  Возведение матрицы оператора в степень:
    int * ptr_A = (int*) A; // Указатель на матрицу оператора
    power(ptr_A, n-1, base);

//  Вычисление n-го члена последовательности:
    int xn = A[0][0]*x1 + A[1][0]*x2;
    mod(&xn, base); // Взятие его по модулю

//  Вывод ответа на экран:
    printf("X(%d) = %d\n", n, xn);

    return 0;
}

void mod(int * val, int n){
//  Функция вычисляет значение val по модулю n
    *val = (*val >= 0) ? (*val % n) : (n-(-*val) % n);
}

void inc(int * val, int n, int k){
//  Функция увеличивает значение val на k по модулю n
    mod(&k, n);
    *val += k;
    mod(val, n);
}

void dec(int * val, int n, int k){
//  Функция уменьшает значение val на k по модулю n
    mod(&k, n);
    *val -= k;
    mod(val, n);
}

void prod(int * A, int * B, int * C, int n){
//  В матрицу C записывается результат умножения матрицы A на матрицу B.
//  Работа ведется в кольце вычетов по модулю n

    int i, j, k, size = 2; // i, j, k - счетчики, size - размерность матриц

//  Напоминание: в указательной арифметике C[i][j] записывается как *(C+size*i+j)
//  При работе с многомерными массивами внутри функции в Си доступна только указательная арифметика

//  Обнуляем все элементы матрицы C:
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++)
            *(C+i*size+j) = 0;

//  В C[i][j] Записываем результат произведения i-ой строки матрицы A на j-ый столбец матрицы B:
    for (i = 0; i < size; i++)
        for (j = 0; j < size; j++)
            for (k = 0; k < size; k++){
                int d = *(A+i*size+k) * *(B+k*size+j); // Произведение A[i][k] на B[k][j]
                inc(C+i*size+j, n, d); // Добавляем к C[i][j] значение d
            }
}

void copy(int * A, int * B){
//  Копирует двумерную матрицу B в матрицу A
    int i, j, size = 2;
    for(i=0; i < size; i++)
        for(j=0; j< size; j++)
            *(A+size*i+j) = *(B+size*i+j);
}

void print(int * A){
//  Выводит двумерную матрицу на экран:
    int i, j, SIZE = 2;
    for (i = 0; i < SIZE; i++, printf("\n"))
        for (j = 0; j < SIZE; j++)
            printf("%d ", *(A+SIZE*i+j));
}

void power(int * A, int k, int n){
//  Быстрым возведением в степень возводит матрицу A в степень k. Значения элементов матрицы берутся по модулю n.
    unsigned const int SIZE = 2;
    int M[SIZE][SIZE]; // Матрица M, в которой будем хранить промежуточные вычисления
    int T[SIZE][SIZE]; // В матрицу T будем записывать эти вычисления, а потом копировать в переменную M

//  Сделаем матрицу M единичной:
    M[0][0] = 1; M[0][1] = 0;
    M[1][0] = 0; M[1][1] = 1;

    int *ptr_M = (int*)M; // Указатель на матрицу M
    int *ptr_T = (int*)T; // Указатель на матрицу T

    while (k > 0){
        if (k % 2 != 0){
            prod(ptr_M, A, ptr_T, n); // T = M * A;
            k--;
        } else {
            prod(ptr_M, ptr_M, ptr_T, n); // T = M^2
            k /= 2;
        }
        copy(ptr_M, ptr_T); // M = T
    }

    copy(A, ptr_M); // Копирование ответа в переменную A
}