矩阵快速幂求斐波那契数列c语言

矩阵快速幂是一种高效的求解斐波那契数列的方法，它可以在O(logn)的时间复杂度内求解第n个斐波那契数。具体实现方法是将斐波那契数列转化为矩阵形式，然后通过矩阵乘法和快速幂算法来求解。下面是一个用C语言实现矩阵快速幂求解斐波那契数列的代码：

#include <stdio.h>

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

void matrix_pow(int a[2][2], int n) {
    int ans[2][2] = {{1, 0}, {0, 1}};
    while (n) {
        if (n & 1) {
            matrix_multiply(ans, a);
        }
        matrix_multiply(a, a);
        n >>= 1;
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = ans[i][j];
        }
    }
}

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    int a[2][2] = {{1, 1}, {1, 0}};
    matrix_pow(a, n - 1);
    return a[0][0];
}

int main() {
    int n;
    printf("请输入要求解的斐波那契数列的项数：");
    scanf("%d", &n);
    printf("第%d项斐波那契数为：%d\n", n, fibonacci(n));
    return 0;
}