快速取模指数算法c++

以下是快速幂取模算法的 C++ 代码实现：

#include <iostream>
using namespace std;

int fast_power(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

int main() {
    int a = 3, b = 7, m = 5;
    int ans = fast_power(a, b, m);
    cout << a << "^" << b << " mod " << m << " = " << ans << endl;
    return 0;
}

其中，`fast_power` 函数接收三个参数 `a`, `b`, `m`，分别表示底数、指数和模数。在函数内部，使用了位运算来快速计算幂次，同时每次计算后都对模数取余，来保证计算结果不会溢出。最后返回计算结果。

在上述代码中，对于 `a=3`, `b=7`, `m=5` 的输入，输出为 `3^7 mod 5 = 3`。

相关问题

快速幂算法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很大时。同时，由于取模运算的存在，可以避免计算结果溢出的问题。

快速幂取模算法java

快速幂取模算法是一种用于计算幂取模的高效算法，它可以在O(logn)的时间复杂度内完成计算。在Java中，可以使用以下代码实现快速幂取模算法：

public static int fastPowMod(int a, int b, int c) {
    int ans = 1;
    a %= c;
    while (b > 0) {
        if ((b & 1) == 1) {
            ans = (ans * a) % c;
        }
        b >>= 1;
        a = (a * a) % c;
    }
    return ans;
}

其中，a、b、c分别为底数、指数和模数，返回值为a^b mod c的结果。该算法的基本思想是将指数b转化为二进制形式，然后根据二进制位上的值来计算幂的乘积，最终得到结果。