斐波那契数列快速幂c++

斐波那契数列是一个经典的数学问题，它的定义是：第一个和第二个数为1，从第三个数开始，每个数都是前两个数的和。即：1, 1, 2, 3, 5, 8, 13, 21, ...

快速幂是一种优化指数运算的算法，可以在较短的时间内计算出较大的指数幂。在斐波那契数列中，我们可以使用快速幂算法来计算第n个斐波那契数。

以下是使用C++实现斐波那契数列快速幂的代码：

#include <iostream>

// 使用快速幂算法计算斐波那契数列
int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }

    int a = 1, b = 1;
    int c = 0, d = 1;
    int temp1, temp2;

    while (n > 0) {
        if (n % 2 == 1) {
            temp1 = a * c + b * d;
            temp2 = b * c + d * (a + b);
            a = temp1;
            b = temp2;
        }

        temp1 = c * c + d * d;
        temp2 = d * (2 * c + d);
        c = temp1;
        d = temp2;

        n /= 2;
    }

    return a;
}

int main() {
    int n;
    std::cout << "请输入要计算的斐波那契数列的位置：";
    std::cin >> n;

    int result = fibonacci(n);
    std::cout << "第" << n << "个斐波那契数是：" << result << std::endl;

    return 0;
}