快速幂运算的c语言代码

快速幂运算是计算a^n模m的有效算法，避免了直接递归计算n次幂的高复杂度。在C语言中，可以使用位运算结合循环来实现这个高效算法。以下是基本的代码示例：

#include <stdio.h>

// 定义快速幂函数
int fastPower(int a, int n, int m) {
    if (n == 0) return 1; // 当指数为0时，结果为1
    int res = 1; // 初始化结果为1

    while (n) { // 如果指数还有剩余
        if (n & 1) res = (res * a) % m; // 如果n为奇数，将当前结果乘以a并取模
        a = (a * a) % m; // 将底数平方并取模，相当于将指数除以2
        n >>= 1; // 右移一位，相当于除以2
    }
    return res;
}

int main() {
    int base = 5, exponent = 100, modulus = 10007;
    printf("5^100 mod 10007 = %d\n", fastPower(base, exponent, modulus));
    return 0;
}

在这个代码中，`fastPower` 函数接收三个参数，分别表示底数、指数和模数。它首先处理特殊情况（n=0），然后用循环将指数不断二分，并利用位运算判断当前是否需要将底数乘入结果。

相关问题

快速幂取模c语言代码

快速幂取模是一种高效的算法，用于计算大整数的幂运算并限制结果在给定的模数范围内。其核心思想是利用指数的二进制表示，将幂次方拆分为一系列较小的乘法，大大减少了乘法次数。以下是C语言中实现快速幂取模的基本代码：

#include <stdio.h>

// 计算 a^b % m 的结果 (快速幂)
long long fastPowMod(long long a, long long b, long long m) {
    long long result = 1; // 初始化结果为1
    while (b > 0) {
        // 如果b是奇数，则将a乘入结果
        if (b & 1) {
            result = (result * a) % m;
        }
        
        // 将b除以2，将a自乘
        a = (a * a) % m;
        b >>= 1; // b右移一位相当于除以2
    }
    return result;
}

int main() {
    long long base, exponent, mod;
    printf("请输入底数、指数和模数：\n");
    scanf("%lld %lld %lld", &base, &exponent, &mod);
    long long powerResult = fastPowMod(base, exponent, mod);
    printf("(%lld)^%lld mod %lld = %lld\n", base, exponent, mod, powerResult);
    return 0;
}

在这个代码里，用户输入底数`base`、指数`exponent`以及一个模数`m`，程序会返回`base`的`exponent`次方对`m`取余的结果。

模幂运算的快速算法c语言代码

以下是快速幂算法的C语言代码：

int FastExponentiation(int base, int exponent, int mod) {
    int result = 1;
    base %= mod;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % mod;
        }
        exponent = exponent >> 1;
        base = (base * base) % mod;
    }
    return result;
}

其中，base表示底数，exponent表示指数，mod表示取模数。这段代码通过位运算的方法快速计算出整数的幂次方，并对mod取余以避免数值溢出等问题。