快速幂算法取余 C++

快速幂算法（也称为幂运算优化算法）是一种用于快速计算一个数的幂次的算法。当需要计算大数的幂时，使用快速幂算法可以显著提高效率。

在C语言中，可以使用以下代码实现快速幂算法取余：

long long fastModularExponentiation(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base = base % modulus;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

在函数中，`base`表示底数，`exponent`表示指数，`modulus`表示取余的模数。函数返回的是`base`的`exponent`次幂对`modulus`取余的结果。

这个算法的核心思想是将指数用二进制表示，然后根据二进制位上的值来决定是否乘以底数，并不断地更新底数的值。通过这种方式，可以减少乘法和取余的次数，从而提高算法的效率。

希望这个解答对你有帮助！如果有任何问题，请随时提问。

相关问题

快速幂算法c++取模

以下是C++实现快速幂取模的代码，其中a为底数，b为指数，mod为模数：

long long quickPow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

该算法的时间复杂度为O(log b)，比普通的幂运算算法要快很多，特别是在指数b很大时。同时，由于取模运算的存在，可以避免计算结果溢出的问题。

矩阵的快速幂算法c++

矩阵的快速幂算法可以用来求解矩阵的幂，在一些数学和计算机科学领域中经常会用到。C++实现如下：

#include <iostream>
#include <vector>

using namespace std;

// 矩阵快速幂
vector<vector<int>> matrixPow(vector<vector<int>>& matrix, int n) {
    int m = matrix.size();  // 矩阵的行数
    vector<vector<int>> res(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++) {
        res[i][i] = 1;  // 初始化为单位矩阵
    }
    while (n > 0) {
        if (n & 1) {
            vector<vector<int>> tmp(m, vector<int>(m, 0));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                    for (int k = 0; k < m; k++) {
                        tmp[i][j] += res[i][k] * matrix[k][j];
                    }
                }
            }
            res = tmp;
        }
        vector<vector<int>> tmp(m, vector<int>(m, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < m; k++) {
                    tmp[i][j] += matrix[i][k] * matrix[k][j];
                }
            }
        }
        matrix = tmp;
        n >>= 1;
    }
    return res;
}

int main() {
    vector<vector<int>> matrix = {{1, 2}, {3, 4}};
    int n = 3;
    vector<vector<int>> res = matrixPow(matrix, n);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[0].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

在上面的程序中，`matrixPow`函数用来计算矩阵`matrix`的`n`次幂，并返回结果`res`。在`while`循环中，通过位运算来计算`n`的二进制表示，如果`n`的二进制表示的最后一位是1，则将`res`与`matrix`相乘得到新的`res`；否则，将`matrix`自乘得到新的`matrix`。最后返回`res`即可。

在`main`函数中，我们使用下面的代码调用`matrixPow`函数，并打印结果。

vector<vector<int>> matrix = {{1, 2}, {3, 4}};
int n = 3;
vector<vector<int>> res = matrixPow(matrix, n);
for (int i = 0; i < res.size(); i++) {
    for (int j = 0; j < res[0].size(); j++) {
        cout << res[i][j] << " ";
    }
    cout << endl;
}

这样就可以输出矩阵`matrix`的`n`次幂了。