洛谷：P1226：快速幂（模板）

题目

P1226：快速幂（模板）

分析

这道题虽说是模版题，但解决了很重要的问题：如何快速求形如\(a^b\)的幂。

基本思路还是分治。以求\(3^{25}\)为例：

\(3^{25}=(3^{12})^2\times 3=((3^6)^2)^2\times 3=(((3^2\times 3)^2)^2)^2\times 3\)

这个算法比循环\(b\)次求解快多了。核心观察：

• 观察一：如果\(b\)是偶数，那么\(result=(a^{b/2})^2\)
• 观察二：如果\(b\)是奇数，那么\(result=(a^{b/2})^2\times a\)¹

解法一：递归

根据上述思路写出递归解法：

long long fastPowRecursive(long long a, long long b, long long p)
{
    if (b == 0)
        return 1;

    long long half = fastPowRecursive(a, b / 2, p);
    half = (half * half) % p;

    if (b % 2 == 1)
    {
        half = (half * a) % p;
    }

    return half;
}

注意：递归终止条件是\(b==0\)。

解法二：递推

上面的解法可以通过，但我们可以用更直接了当的递推来解题：

long long fastPow(long long a, long long b, long long p)
{
    long long result = 1;
    a = a % p;  // Handle case where a >= p

    while (b > 0)
    {
        // b是奇数，需要单独乘一次
        if (b & 1)
        {
            result = (result * a) % p;
        }

        // 无论如何，b减半，a平方
        b = b >> 1;       // b = b / 2
        a = (a * a) % p;  // a = a^2
    }

    return result;
}

答案

思考

对于两个算法，时间复杂度都是\(O(log b)\)。