快速模幂运算c++代码

下面是一个快速模幂运算的 C 代码实现：

#include <stdio.h>

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

int main() {
    int base = 3;
    int exponent = 7;
    int modulus = 5;
    int result = mod_pow(base, exponent, modulus);
    printf("%d^%d mod %d = %d\n", base, exponent, modulus, result);
    return 0;
}

该代码实现了一个函数 `mod_pow`，它接受三个参数：底数 `base`、指数 `exponent` 和模数 `modulus`，并返回一个整数值，表示底数的指数次幂对模数取余的结果。

该函数使用了快速幂算法，它通过将指数 `exponent` 拆分成二进制位的形式，可以在 $O(\log_2 n)$ 的时间复杂度内计算出底数的指数次幂对模数取余的结果。该算法的基本思想是，如果 $a^{n}$ 可以被表示为 $a^{n} = a^{k_0} \cdot a^{k_1} \cdot a^{k_2} \cdots a^{k_{m-1}}$，其中 $k_0, k_1, k_2, \cdots, k_{m-1}$ 是 $n$ 的二进制位，那么可以通过逐个计算 $a^{2^i}$，并根据 $n$ 的二进制位来选择哪些 $a^{2^i}$ 需要相乘，从而计算出 $a^{n}$ 的值。