c++语言实现快速幂模算法

好的，下面是 C++ 实现快速幂模算法的代码：

long long quick_pow_mod(long long a, long long b, long long m) {
    long long ans = 1;
    a %= m;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

其中 `a` 表示底数，`b` 表示指数，`m` 表示模数。该函数返回的是 `a^b % m` 的值。

算法的思路是将指数 `b` 二进制拆分，每次将底数 `a` 自乘，如果当前二进制位是 1，则乘上当前底数，最后将结果对模数 `m` 取模得到结果。

这个算法可以用于解决一些数论问题，如求解离线查询的快速幂、快速幂求逆元等。

相关问题

用C++写一个矩阵快速幂

好的，以下是用 C 语言写一个矩阵快速幂的示例代码：

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

#define MAXN 100

typedef struct {
    int n, m;
    int a[MAXN][MAXN];
} Matrix;

Matrix matMul(Matrix A, Matrix B) {
    Matrix C;
    C.n = A.n, C.m = B.m;
    for (int i = ; i < C.n; i++) {
        for (int j = ; j < C.m; j++) {
            C.a[i][j] = ;
            for (int k = ; k < A.m; k++) {
                C.a[i][j] += A.a[i][k] * B.a[k][j];
            }
        }
    }
    return C;
}

Matrix matPow(Matrix A, int p) {
    Matrix ans;
    ans.n = ans.m = A.n;
    for (int i = ; i < ans.n; i++) {
        for (int j = ; j < ans.m; j++) {
            ans.a[i][j] = (i == j);
        }
    }
    while (p) {
        if (p & 1) ans = matMul(ans, A);
        A = matMul(A, A);
        p >>= 1;
    }
    return ans;
}

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    Matrix A;
    A.n = A.m = n;
    for (int i = ; i < n; i++) {
        for (int j = ; j < n; j++) {
            scanf("%d", &A.a[i][j]);
        }
    }
    Matrix ans = matPow(A, m);
    printf("%d\n", ans.a[k - 1][]);
    return ;
}

这个程序可以计算一个 n × n 的矩阵 A 的 m 次方，然后输出第 k 行第 1 列的元素。其中，矩阵 A 的元素从标准输入中读入。

用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`函数中，我们可以自定义输入矩阵维度、矩阵内容以及幂指数，并输出矩阵求幂的结果。