用C语言实现快速幂矩阵

下面是用C语言实现快速幂矩阵的代码：

#include <stdio.h>

#define N 2

void matrix_mul(int a[][N], int b[][N], int c[][N]) {
    int i, j, k;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            c[i][j] = 0;
            for (k = 0; k < N; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

void matrix_copy(int a[][N], int b[][N]) {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            a[i][j] = b[i][j];
        }
    }
}

void matrix_pow(int a[][N], int n, int b[][N]) {
    int i, j, k;
    int res[N][N] = { {1, 0}, {0, 1} };
    while (n > 0) {
        if (n & 1) {
            matrix_mul(res, a, res);
        }
        matrix_mul(a, a, a);
        n >>= 1;
    }
    matrix_copy(b, res);
}

int main() {
    int a[N][N] = { {1, 1}, {1, 0} };
    int b[N][N];
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    matrix_pow(a, n, b);
    printf("The %d-th Fibonacci number is %d\n", n, b[0][1]);
    return 0;
}

解释如下：

1. `matrix_mul` 函数用于计算两个矩阵的乘积。

2. `matrix_copy` 函数用于将一个矩阵复制到另一个矩阵中。

3. `matrix_pow` 函数用于计算矩阵 a 的 n 次幂，结果存储在矩阵 b 中。

4. 在 `main` 函数中，首先定义一个矩阵 a，它表示斐波那契数列的递推关系。然后输入要求的斐波那契数列的项数 n，调用 `matrix_pow` 函数计算矩阵 a 的 n 次幂，结果存储在矩阵 b 中。最后输出第 n 项斐波那契数列的值。