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

写一段长形整数下的长形整数次幂运算取模c++语言算法

在 C++ 中，处理大整数（如长整型）的次方运算并取模通常涉及到高效的算法，比如快速幂算法（Fast Exponentiation）。这个算法利用了指数的二进制表示，避免直接对大整数进行多次乘法。

以下是一个使用迭代快速幂算法的 C++ 代码示例，用于计算长形整数 a 的 b 次幂取模 c：

#include <vector>
#include <string>

// 将字符串转换为长整型
long long int strToLong(const std::string &str) {
    long long int result = 0;
    for (char c : str) {
        if (isdigit(c))
            result = result * 10 + c - '0';
    }
    return result;
}

// 快速幂取模
long long int fastPowerMod(long long int base, long long int exponent, long long int modulus) {
    long long int result = 1;
    base %= modulus; // 取模操作，防止溢出

    while (exponent > 0) {
        // 如果指数是奇数，则将结果乘以base并取模
        if (exponent % 2 == 1)
            result = (result * base) % modulus;

        // 将指数除以2并平方base
        exponent /= 2;
        base = (base * base) % modulus;
    }

    return result;
}

int main() {
    std::string num_str1, num_str2, mod_str;
    std::cout << "Enter the first number: ";
    std::getline(std::cin, num_str1);
    std::cout << "Enter the second power: ";
    std::cin >> num_str2;
    std::cout << "Enter the modulus: ";
    std::cin >> mod_str;

    long long int a = strToLong(num_str1);
    long long int b = strToLong(num_str2);
    long long int c = strToLong(mod_str);

    long long int result = fastPowerMod(a, b, c);
    std::cout << "Result (modulus): " << result << "\n";

    return 0;
}

在这个例子中，`strToLong` 函数用于将输入的字符串转换为长整型，然后 `fastPowerMod` 函数实现了快速幂算法，最后在 `main` 函数中调用这些功能。