快速幂

【快速幂】是一种高效计算大数幂的算法技术，可以将计算时间从 O(n) 降低到 O(log n)。在ACM竞赛中，它是解决大数乘方问题的必备技能。

基本原理

快速幂的核心思想是利用幂运算的性质，将指数分解为二进制表示，从而减少计算次数。

例如，计算 a^11：

11 的二进制表示为 1011
因此 a^11 = a^8 a^2 a^1
只需要计算 a^1, a^2, a^4, a^8 即可

迭代实现

// 计算 a^b 的值
long long quickPow(long long a, long long b) {
    long long res = 1; // 初始化结果为1

    while (b > 0) {
        if (b & 1) {  // 如果b的当前最低位为1
            res = res * a;  // 将当前的a累乘到结果中
        }
        a = a * a;  // a平方
        b >>= 1;  // b右移一位，即b = b/2
    }

    return res;
}

递归实现

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

    long long half = quickPow(a, b / 2);

    if (b % 2 == 0) {
        return half * half;
    } else {
        return half * half * a;
    }
}

取模快速幂

在实际竞赛中，通常需要对结果取模，以避免整数溢出：

// 计算 (a^b) % mod
long long quickPowMod(long long a, long long b, long long mod) {
    a %= mod;
    long long res = 1;

    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

时间复杂度分析

普通幂运算：O(n)
快速幂：O(log n)

对于大指数，快速幂的效率提升是非常显著的。

应用场景

大数幂模运算：如 RSA 加密算法
矩阵快速幂：解决斐波那契数列、路径计数等问题
组合数学：计算大组合数
乘法逆元：在模运算中求解乘法逆元

典型例题

例题1：模幂运算

问题：计算 (a^b) % m，其中 1 ≤ a, b, m ≤ 10^9

解法：直接应用取模快速幂算法

例题2：矩阵快速幂计算斐波那契数列

问题：计算第n个斐波那契数 F(n)，其中 F(1) = F(2) = 1，F(n) = F(n-1) + F(n-2)

解法：

将状态转移方程表示为矩阵乘法形式
使用矩阵快速幂求解

struct Matrix {
    long long a[2][2];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % MOD;
        return res;
    }
};

long long fibonacci(long long n) {
    if (n <= 2) return 1;

    Matrix base;
    base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;
    base.a[1][1] = 0;

    Matrix res;
    res.a[0][0] = res.a[1][1] = 1;

    n -= 2;
    while (n) {
        if (n & 1) res = res * base;
        base = base * base;
        n >>= 1;
    }

    return (res.a[0][0] + res.a[0][1]) % MOD;
}

注意事项

【防止溢出】：在计算过程中注意取模，避免中间结果溢出
【处理特殊情况】：注意处理b=0，a=0等边界情况
【负指数】：当需要计算负指数时，可以利用 a^(-b) = 1/(a^b)

常见错误

中间计算结果溢出
忘记对中间结果取模
递归实现时没有正确处理基础情况

练习题目推荐

POJ 1995 - Raising Modulo Numbers
CodeForces 630I - Parking Lot
SPOJ - LASTDIG