C语言快速幂算法详解（小白也能学会的高效幂运算技巧）

C语言快速幂基础实现

下面是一个不带取模的快速幂函数：

long long fast_pow(long long base, long long exp) {    long long result = 1;    while (exp > 0) {        // 如果当前指数是奇数，就把当前 base 乘到结果中        if (exp % 2 == 1) {            result = result * base;        }        // 指数除以2（右移一位）        exp = exp / 2;        // base 平方        base = base * base;    }    return result;}

这个函数的时间复杂度是 O(log n)，比普通循环快得多。

快速幂取模（更实用的版本）

在实际编程竞赛或工程中，我们常常需要计算 (a^n) mod m，防止结果溢出。这时要用到快速幂取模，利用模运算的性质：(a * b) mod m = ((a mod m) * (b mod m)) mod m。

long long fast_pow_mod(long long base, long long exp, long long mod) {    long long result = 1;    base = base % mod; // 先取模，防止 base 太大    while (exp > 0) {        if (exp % 2 == 1) {            result = (result * base) % mod;        }        exp = exp >> 1; // 等价于 exp /= 2，但位运算更快        base = (base * base) % mod;    }    return result;}

注意这里使用了位运算 exp >> 1 来代替除法，效率更高。

完整示例：计算 2^10 mod 1000

#include <stdio.h>long long fast_pow_mod(long long base, long long exp, long long mod) {    long long result = 1;    base %= mod;    while (exp > 0) {        if (exp & 1) { // 判断奇偶：exp & 1 等价于 exp % 2 == 1            result = (result * base) % mod;        }        exp >>= 1;        base = (base * base) % mod;    }    return result;}int main() {    long long a = 2, n = 10, m = 1000;    printf("%lld^%lld mod %lld = %lld\n", a, n, m, fast_pow_mod(a, n, m));    // 输出：2^10 mod 1000 = 24    return 0;}

为什么学习C语言快速幂算法？

掌握C语言幂运算优化技巧，不仅能提升程序效率，还是学习更高级算法（如矩阵快速幂、RSA加密）的基础。对于准备编程竞赛或面试的同学来说，算法入门教程中的快速幂是必学内容。

小结

- 快速幂将 O(n) 优化为 O(log n)
- 核心：二进制拆分 + 平方加速
- 实际应用中通常配合取模操作
- 是每位 C 语言学习者应掌握的快速幂取模基本功

现在你已经学会了 C 语言快速幂算法！快去试试解决一些幂运算问题吧～