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

C语言中使用矩阵快速幂可以高效地求解斐波那契数列。矩阵快速幂是一种基于矩阵乘法的算法，通过将斐波那契数列的递推关系转化为矩阵形式，可以在O(logn)的时间复杂度内求解第n个斐波那契数。

首先，我们定义一个2x2的矩阵F，其中F表示第0个斐波那契数，F表示第1个斐波那契数，F表示第2个斐波那契数，F表示第3个斐波那契数。初始时，F的值为：

F = {{1, 1},
     {1, 0}}

然后，我们定义一个2x2的单位矩阵I，其中I和I为1，其余元素为0。初始时，I的值为：

I = {{1, 0},
     {0, 1}}

接下来，我们使用矩阵快速幂的方法来计算F的n次幂。具体步骤如下：
1. 将n转化为二进制形式。
2. 从二进制形式的最低位开始，依次遍历每一位。
3. 如果当前位为1，将矩阵F乘以矩阵I，并将结果保存到矩阵I中。
4. 将矩阵F自乘，即将矩阵F乘以矩阵F，并将结果保存到矩阵F中。
5. 继续遍历下一位，直到遍历完所有位。

最后，当遍历完所有位后，矩阵I中的值即为F的n次幂。其中，I即为第n个斐波那契数。

下面是C语言中使用矩阵快速幂求解斐波那契数列的代码示例：

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]) {
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(int F[2][2], int n) {
    if (n <= 1) {
        return;
    }

    int M[2][2] = {{1, 1}, {1, 0}};
    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0) {
        multiply(F, M);
    }
}

int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }

    int F[2][2] = {{1, 1}, {1, 0}};
    power(F, n - 1);

    return F[0][0];
}

int main() {
    int n = 10;
    int result = fibonacci(n);
    printf("第%d个斐波那契数为：%d\n", n, result);

    return 0;
}

以上代码中，我们定义了两个函数`multiply`和`power`，分别用于矩阵相乘和计算矩阵的n次幂。`fibonacci`函数用于计算第n个斐波那契数。在`main`函数中，我们调用`fibonacci`函数计算第10个斐波那契数，并将结果打印输出。