首页快速幂算法C语言

快速幂算法C语言

时间: 2025-06-01 19:17:11 浏览: 11

快速幂算法是一种高效的计算指数运算 \(a^b \mod c\) 的方法。相比传统的逐次相乘法，它的时间复杂度从 O(b) 降低到了 O(log b)，极大地提升了效率。以下是快速幂的核心思想及其在 C 语言中的实现： ### 核心原理 1. 如果指数 \(b\) 是偶数，则有公式： \( a^b = (a^{b/2})^2 \) 2. 如果指数 \(b\) 是奇数，则可以拆解为： \( a^b = a \cdot a^{(b-1)} \) 通过不断将指数折半，并利用模运算的性质 (\((x*y)\%c=(x\%c * y\%c)\%c\)) 避免溢出，我们能有效减少乘法次数。 --- ### 示例代码 ```c #include <stdio.h> // 定义快速幂函数 long long quick_pow(long long base, long long exp, long long mod){ long long result = 1; // 初始化结果为1 while(exp > 0){ if(exp % 2 == 1){ // 判断当前指数是否为奇数 result = (result * base) % mod; } base = (base * base) % mod; // 每轮都将底数平方并取模 exp /= 2; // 指数减半 } return result; } int main(){ long long a = 3, b = 5, m = 7; printf("Result of %lld^%lld mod %lld is: %lld\n", a, b, m, quick_pow(a,b,m)); return 0; } ``` **说明**: 上述程序实现了求解 \(3^5 \mod 7\) 并打印最终的结果。 --- ### 算法特点 1. **高效性**：通过对指数反复折半操作大幅减少了所需的循环次数； 2. **广泛适用性**：不仅适用于整型数据范围内的简单情况，在处理大素数、加密等领域也有广泛应用。

阅读全文