快速幂算法原理与实现：高效计算大数幂取模

1. 快速幂算法原理与实现

快速幂算法（Fast Exponentiation）是一种高效计算大数幂取模的算法，特别适用于计算a^b mod p这类问题。传统暴力计算法的时间复杂度是O(b)，而快速幂算法可以优化到O(log b)，这在处理大指数时优势尤为明显。

1.1 算法核心思想

快速幂算法的核心在于将指数b进行二进制分解。举个例子，计算3^13时：

• 13的二进制表示为1101
• 因此3^13 = 3^(8+4+1) = 3^8 × 3^4 × 3^1

通过这种分解，我们可以利用平方操作来快速计算各个分量：

• 3^1 = 3
• 3^2 = (3^1)^2 = 9
• 3^4 = (3^2)^2 = 81
• 3^8 = (3^4)^2 = 6561

最终只需要将需要的分量相乘：3^13 = 6561 × 81 × 3 = 1594323

1.2 模运算优化

在实际应用中，我们通常需要计算的是a^b mod p。直接计算a^b会导致数值过大而溢出，因此需要在每一步都进行模运算：

cpp复制long long qPow(long long a, long long b, long long p) {
    long long res = 1;
    a = a % p; // 初始取模
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

2. 代码实现详解

2.1 函数参数与初始化

cpp复制long long qPow(long long a, long long b, long long p) {
    long long res = 1, base = a;
    // ...
}

• a：底数
• b：指数
• p：模数
• res：存储结果的变量，初始化为1（任何数的0次方都是1）
• base：当前计算的基数，初始化为a

2.2 主循环逻辑

cpp复制while(b) {