用c++实现一个快速幂代码

以下是使用C++实现快速幂的代码示例：

#include <iostream>
using namespace std;

// 计算 a^b 的值
int fastPow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {    // 判断 b 是否为奇数
            res *= a;
        }
        a *= a; // a 每次平方
        b >>= 1;    // b 右移一位，相当于除以 2
    }
    return res;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << fastPow(a, b) << endl;
    return 0;
}

这里使用了位运算和循环来实现快速幂，可以将时间复杂度降为 O(log b)。

相关问题

用c++实现一个快速幂

以下是C语言实现快速幂的代码：

#include <stdio.h>

long long fast_pow(int base, int exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    return result;
}

int main() {
    int base = 2, exponent = 10;
    long long result = fast_pow(base, exponent);
    printf("%d^%d = %lld\n", base, exponent, result);
    return 0;
}

该代码使用了位运算实现了快速幂算法，可以提高计算效率。在该算法中，我们使用了一个while循环，每次将指数折半，将底数平方，如果指数的二进制位为1，则将结果乘上底数。最后返回结果即可。

用c++写一个矩阵快速幂的代码

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

#include <stdio.h>
#include <stdlib.h>

#define MAXN 10

typedef struct matrix {
    int m[MAXN][MAXN];
} Matrix;

Matrix mul(Matrix a, Matrix b, int n) {
    Matrix c;
    int i, j, k;
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            c.m[i][j] = 0;
            for (k = 0; k < n; ++k) {
                c.m[i][j] += a.m[i][k] * b.m[k][j];
            }
        }
    }
    return c;
}

Matrix pow(Matrix a, int n, int k) {
    Matrix res;
    int i, j;
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            res.m[i][j] = (i == j) ? k : 0;
        }
    }
    while (n > 0) {
        if (n & 1) {
            res = mul(res, a, k);
        }
        a = mul(a, a, k);
        n >>= 1;
    }
    return res;
}

int main() {
    int n, k, i, j;
    Matrix a;
    printf("请输入矩阵的大小n和幂次k：");
    scanf("%d%d", &n, &k);
    printf("请输入矩阵A：\n");
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            scanf("%d", &a.m[i][j]);
        }
    }
    Matrix res = pow(a, k, n);
    printf("矩阵A的%d次幂为：\n", k);
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            printf("%d ", res.m[i][j]);
        }
        printf("\n");
    }
    return 0;
}

该代码中，`Matrix` 结构体表示一个矩阵，`mul()` 函数实现了矩阵的乘法，`pow()` 函数实现了矩阵的快速幂。在 `main()` 函数中，先输入矩阵的大小和幂次，然后输入矩阵 A，最后输出 A 的 k 次幂。

### 回答2：
矩阵快速幂是一种快速计算矩阵乘法的方法，可以在 O(log n) 的时间复杂度内计算一个矩阵的 n 次方。下面是用 C 语言编写一个矩阵快速幂的代码示例：

#include <stdio.h>

#define N 2  // 矩阵的大小

// 矩阵乘法
void multiplyMatrix(int a[N][N], int b[N][N], int result[N][N]) {
    int i, j, k;
    int temp[N][N];
    
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            temp[i][j] = 0;
            for (k = 0; k < N; k++) {
                temp[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    
    // 将结果复制到 result 矩阵中
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            result[i][j] = temp[i][j];
        }
    }
}

// 矩阵快速幂
void matrixPower(int base[N][N], int exponent, int result[N][N]) {
    int i;
    int temp[N][N];
    
    // 初始化结果矩阵为单位矩阵
    for (i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) {
                result[i][j] = 1;
            } else {
                result[i][j] = 0;
            }
        }
    }
    
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            multiplyMatrix(result, base, temp);
            // 将结果复制到 result 矩阵中
            for (i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    result[i][j] = temp[i][j];
                }
            }
        }
        
        multiplyMatrix(base, base, temp);
        // 将结果复制到 base 矩阵中
        for (i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                base[i][j] = temp[i][j];
            }
        }
        
        exponent /= 2;
    }
}

// 打印矩阵
void printMatrix(int matrix[N][N]) {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int base[N][N] = {{1, 1}, {1, 0}};
    int exponent = 5;
    int result[N][N];
    
    matrixPower(base, exponent, result);
    printMatrix(result);
    
    return 0;
}

以上代码演示了如何使用 C 语言编写一个矩阵快速幂的程序。程序中先定义了一个矩阵乘法函数 `multiplyMatrix`，用于计算两个矩阵相乘的结果。然后实现了矩阵快速幂函数 `matrixPower`，用于计算一个矩阵的指数次方。最后在 `main` 函数中使用示例矩阵和指数调用 `matrixPower` 函数，并通过 `printMatrix` 函数打印结果。

### 回答3：
矩阵快速幂是指将一个矩阵求幂的运算使用快速幂算法进行优化，以提高计算的效率。下面是用C语言编写的一个矩阵快速幂算法的示例代码：

#include <stdio.h>

// 定义矩阵的最大维度
#define MAX_SIZE 10

// 矩阵相乘函数
void matrix_multiply(int n, int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE]) {
    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_power(int n, int a[][MAX_SIZE], int m, int b[][MAX_SIZE]) {
    int i, j;
    // 初始化结果矩阵为单位矩阵
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            if(i == j) {
                b[i][j] = 1;
            } else {
                b[i][j] = 0;
            }
        }
    }
    // 进行快速幂运算
    while(m > 0) {
        if(m % 2 == 1) {
            int c[MAX_SIZE][MAX_SIZE];
            matrix_multiply(n, b, a, c);
            for(i=0; i<n; i++) {
                for(j=0; j<n; j++) {
                    b[i][j] = c[i][j];
                }
            }
        }
        int c[MAX_SIZE][MAX_SIZE];
        matrix_multiply(n, a, a, c);
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                a[i][j] = c[i][j];
            }
        }
        m = m / 2;
    }
}

int main() {
    int n = 3; // 矩阵维度
    int a[MAX_SIZE][MAX_SIZE] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 输入矩阵
    int m = 3; // 幂指数
    int b[MAX_SIZE][MAX_SIZE]; // 结果矩阵
    matrix_power(n, a, m, b);
    // 输出结果矩阵
    int i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

以上代码实现了一个矩阵快速幂算法，其中`matrix_multiply`函数用于计算两个矩阵的乘积，`matrix_power`函数用于进行矩阵的快速幂运算。在`main`函数中，我们可以自定义输入矩阵维度、矩阵内容以及幂指数，并输出矩阵求幂的结果。