#c

C++倍增法基础——快速幂

高效幂运算的进阶算法技巧

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 倍增法概述

1.1 指数幂运算法则

指数幂的基本运算法则：

  • 乘方法则：
  • 幂的幂法则：
  • 幂的分配律：
  • 二进制拆分：任何正整数n可表示为，其中
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

1.2 倍增法的幂次拆分

  1. 幂次计算：
  1. 计算的拆分：
    • 因此 =
    • 只需要进行7次平方运算即可
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

1.2 倍增法的幂次拆分(续)

  • 计算的拆分：
    • ₂
    • 因此
    • 只需要计算、、并相乘
1 1 0 0 1 0 0
6 5 4 3 2 1 0
64 32 16 8 4 2 1
64 32 4
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

1.3 倍增法概述

  • 倍增法(Binary Lifting) : 是一种基于二进制拆分的高效算法技巧
  • 核心思想：将操作按照2的幂次进行预处理，从而将时间复杂度从降低到
  • 基本原理：任何正整数都可以表示为若干个2的幂次之和，因此可以将次操作分解为最多次预处理过的操作
  • 倍增法的主要应用：
    • 快速幂：快速计算
    • 稀疏表(ST表)：解决区间最值查询(RMQ)问题
    • 最近公共祖先(LCA)：快速查找树中两个节点的最近公共祖先
    • 带权并查集：处理路径压缩和权值更新
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

1.4 倍增法的历史与应用

倍增法的历史：

  • 倍增思想可追溯到古代的快速乘法算法
  • 在计算机科学中，倍增法作为一种优化技术被广泛应用
  • 1973年，Tarjan提出了使用倍增法解决LCA问题的思路
  • 1983年，Berkman和Vishkin提出了使用倍增法构建ST表
  • 现代竞赛算法中，倍增法是解决各类问题的重要工具

倍增法的应用领域：

  • 图论算法（最短路径、最小生成树）
  • 字符串处理（后缀数组、字符串匹配）
  • 计算几何（凸包、最近点对）
  • 数论计算（模幂运算、大整数运算）
  • 数据结构优化（跳表、树上操作）

倍增法与二分法的联系与区别：

  • 联系：
    • 都利用了二分的思想
    • 都能将时间复杂度从降低到
    • 都是算法优化的重要技巧
  • 区别：
    • 二分法主要用于查找和决策
    • 倍增法主要用于预处理和快速计算
    • 二分法每次排除一半可能性
    • 倍增法每次跳跃2的幂次距离
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

2. 倍增法的特点

2.1 倍增法的特点

  • 高效性：时间复杂度为，适用于处理大规模数据
  • 预处理思想：通过预处理2的幂次步长，实现快速跳跃
  • 二进制拆分：利用任何整数都可以表示为2的幂次和的性质
  • 空间换时间：通常需要额外的空间存储预处理结果
  • 适用范围广：从基础的快速幂到复杂的图论问题都有应用
  • 实现相对复杂：比简单的线性算法实现更复杂，但效率更高
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

2.2 倍增法的优势与局限性

倍增法的优势：

  • 高效：将的操作优化到
  • 灵活：可以应用于多种问题类型
  • 可扩展：易于与其他算法技巧结合
  • 预处理后查询快速：适合多次查询的场景
  • 适合处理动态问题：某些情况下可以支持动态更新
  • 数值稳定：不受数据分布影响，性能稳定

倍增法的局限性：

  • 预处理开销：需要的预处理时间
  • 空间需求：通常需要的额外空间
  • 实现复杂度：比直接算法实现更复杂
  • 不适合小规模数据：对于小规模数据，简单算法可能更快
  • 更新成本高：数据变化时可能需要重新预处理
  • 不适合所有问题：某些问题没有明显的倍增结构
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

2.3 倍增法的适用场景

  1. 快速幂运算
    • 计算，其中n可能很大
    • 模幂运算(a^n mod m)
    • 矩阵快速幂（用于解决线性递推关系）
  2. 树上问题
    • 最近公共祖先(LCA)查询
    • 树上路径最值查询
    • 树上距离计算
    • 树上跳跃操作
  1. 区间查询问题
    • 区间最值查询(RMQ)
    • 区间和查询
    • 区间GCD查询
  2. 其他应用
    • 带权并查集
    • 跳表实现
    • 字符串的周期查询
    • 图论中的路径压缩
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

2.4 倍增法的注意事项与优化

何时使用倍增法：

  1. 问题可以分解为重复的相同操作
  2. 操作次数可能很大（需要优化到对数级别）
  3. 可以预处理2的幂次操作结果
  4. 多次查询场景（预处理一次，多次使用）
  5. 问题具有可组合性（较大步长的操作可以由较小步长组合）

倍增法的常见优化：

  • 使用位运算优化2的幂次计算：1 << j代替pow(2, j)
  • 结合记忆化搜索减少冗余计算
  • 使用稀疏存储减少空间开销
  • 动态倍增：支持在线更新的倍增结构
  • 与其他算法结合：倍增+贪心、倍增+动态规划等
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3. 快速幂模板代码

3.1 快速幂模板

// 计算 a^n
long long fastPow(long long a, long long n) {
    long long result = 1;
    
    while (n > 0) {
        // 如果n的当前最低位为1，将a^(2^j)计入结果
        if (n & 1) {
            result = result * a;
        }
        
        // 计算下一个幂次：a^(2^(j+1)) = a^(2^j) * a^(2^j)
        a = a * a;
        
        // 右移一位，处理下一个二进制位
        n >>= 1;
    }
    
    return result;
}

// 计算 a^n
long long fastPow(long long a, long long n) {
    long long result = 1;
    
    for(; n; n >>= 1){
        if(n & 1){
            result = result * a;
        }
        a = a * a;
    }
    
    return result;
}
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.2 模幂运算模板

// 计算 (a^n) % mod
long long modPow(long long a, long long n, long long mod) {
    long long result = 1;
    
    // 确保a在mod范围内
    a %= mod;
    
    while (n > 0) {
        // 如果n的当前最低位为1，将a^(2^j)计入结果
        if (n & 1) {
            result = (result * a) % mod;
        }
        
        // 计算下一个幂次：a^(2^(j+1)) = a^(2^j) * a^(2^j)
        a = (a * a) % mod;
        
        // 右移一位，处理下一个二进制位
        n >>= 1;
    }
    
    return result;
}
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.3 快速乘法原理推导

快速乘法的基本原理：

  • 类似快速幂，快速乘法也利用二进制拆分
  • 将乘法转化为加法的组合
  • 基于倍增思想，避免重复计算

原理推导：

设计算，将表示为二进制形式：
，其中，则：

每一步迭代：

  1. 如果，将当前的加入结果
  2. 翻倍（左移一位）
  3. 右移一位

示例推导：

计算：

  1. 7的二进制表示：
  2. 因此：



  3. 计算过程：
    • 初始：result = 0, a = 13
    • 第1次：b末位为1，result += 13，a *= 2
    • 第2次：b末位为1，result += 26，a *= 2
    • 第3次：b末位为1，result += 52
    • 最终：result = 91
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.4 快速乘模板

// 计算 (a * b) % mod，避免大数乘法溢出
long long quickMultiply(long long a, long long b, long long mod) {
    long long result = 0;
    
    // 确保a和b在mod范围内
    a %= mod;
    b %= mod;
    
    while (b > 0) {
        // 如果b的当前最低位为1，将a计入结果
        if (b & 1) {
            result = (result + a) % mod;
        }
        
        // 将a翻倍
        a = (a + a) % mod;
        
        // 右移一位，处理下一个二进制位
        b >>= 1;
    }
    
    return result;
}

快速乘的应用场景：

  • 大数乘法：当a和b都很大时，直接相乘可能导致溢出
  • 矩阵乘法：在矩阵快速幂中用于矩阵元素的乘法运算
  • 高精度计算：在需要精确计算大数乘积的场景

快速乘的原理：

  • 类似快速幂，将乘法分解为加法的组合
  • 利用二进制拆分，将b表示为2的幂次和
  • 对于b的每个二进制位，如果为1，则将对应的a的倍数加入结果
  • 每次迭代，a翻倍（相当于左移一位）
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.5 矩阵快速幂与斐波那契数列

矩阵乘法基本概念：

  • 矩阵乘法
  • 结果矩阵的元素计算：

斐波那契数列的矩阵表示：

表示斐波那契数列第n项，有：

令，则：

矩阵快速幂推导：

  1. 初始状态：

  2. 转移矩阵的计算：

    • 使用倍增思想
    • 将n表示为二进制形式
    • 预处理的值

  3. 示例：计算

    • 最终结果：

时间复杂度：

返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.5.1 矩阵快速幂代码实现

// 矩阵结构体
struct Matrix {
    vector<vector<long long>> mat;
    int rows, cols;
    
    // 构造函数
    Matrix(int r, int c) : rows(r), cols(c) {
        mat.resize(r, vector<long long>(c, 0));
    }
    
    // 单位矩阵
    static Matrix identity(int n) {
        Matrix res(n, n);
        for (int i = 0; i < n; i++) {
            res.mat[i][i] = 1;
        }
        return res;
    }
    
    // 矩阵乘法
    Matrix operator * (const Matrix& other) const {
        Matrix res(rows, other.cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < other.cols; j++) {
                for (int k = 0; k < cols; k++) {
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

// 矩阵快速幂
Matrix matrixPow(Matrix base, long long exp) {
    Matrix res = Matrix::identity(base.rows);
    
    while (exp > 0) {
        if (exp & 1) {
            res = res * base;
        }
        base = base * base;
        exp >>= 1;
    }
    
    return res;
}

// 计算斐波那契数列第n项
long long fibonacci(long long n) {
    if (n <= 1) return n;
    
    // 定义转移矩阵
    Matrix base(2, 2);
    base.mat[0][0] = 1; base.mat[0][1] = 1;
    base.mat[1][0] = 1; base.mat[1][1] = 0;
    
    // 计算矩阵的n-1次幂
    Matrix res = matrixPow(base, n - 1);
    
    // 初始状态 [F1, F0] = [1, 0]
    return res.mat[0][0]; // F_n
}
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

3.6 倍增法的常见错误与注意事项

快速幂的常见错误与注意事项

  • 整数溢出：在快速幂等计算中，中间结果可能会溢出，需要适当处理（如取模）
  • 边界条件处理：注意n=0、n=1等特殊情况的处理
  • 负数处理：确保算法能够正确处理负指数的情况
  • 位运算错误：确保位运算的正确性，特别是n & 1和n >>= 1的使用
  • 初始化错误：result的初始化要正确，通常初始化为1
  • 循环条件：确保while循环的终止条件正确
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

4. 快速幂实例分析

4.1 实例分析：快速幂计算

问题描述：
计算，其中a是一个整数，n是一个非负整数，可能非常大。

分析：

  • 朴素算法需要O(n)的时间复杂度，对于大的n不可行
  • 利用倍增思想，可以将时间复杂度降低到O(log n)
  • 核心思想：将n表示为二进制形式，然后利用的递推关系
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

4.1 实例分析：快速幂计算（计算过程）

计算的过程：

  1. 将13转换为二进制：
  2. 因此，
  3. 计算各个幂次：
  4. 根据13的二进制表示，我们需要：

快速幂的优势：

  • 只需要计算O(log n)次乘法，而不是O(n)次
  • 对于大的n，效率提升显著
  • 可以轻松处理模幂运算，避免溢出

代码实现：

long long fastPow(long long a, long long n) {
    long long result = 1;
    
    while (n > 0) {
        if (n & 1) {
            result = result * a;
        }
        a = a * a;
        n >>= 1;
    }
    
    return result;
}

// 计算3^13
void example() {
    long long result = fastPow(3, 13);
    cout << "3^13 = " << result << endl;
    // 输出: 3^13 = 1594323
}

复杂度分析：

  • 时间复杂度：O(log n)，因为n的二进制表示有O(log n)位
  • 空间复杂度：O(1)，只使用了常数额外空间
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

5. 练习题推荐

5.1 基础练习题

  1. [POJ 3263] Tallest Cow

    • 难度：★★☆☆☆
    • 描述：使用倍增法处理区间信息
    • 知识点：倍增基础应用

  2. [Codeforces 1175D] Array Splitting

    • 难度：★★☆☆☆
    • 描述：使用倍增法优化区间操作
    • 知识点：倍增与前缀和

  3. [CSES 1095] Exponentiation

    • 难度：★★☆☆☆
    • 描述：计算a^b mod c
    • 知识点：快速幂基础
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

5.2 中级练习题

  1. [CSES 1713] Counting Divisors

    • 难度：★★★☆☆
    • 描述：使用倍增法优化因数计算
    • 知识点：倍增与数论

  2. [CSES 1135] Distance Queries

    • 难度：★★★☆☆
    • 描述：计算树上两点之间的距离
    • 知识点：LCA与树上距离

  3. [CSES 1734] Distinct Values Queries

    • 难度：★★★☆☆
    • 描述：使用倍增法处理区间查询
    • 知识点：倍增与莫队算法
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

6. 总结

6.1 总结

快速幂的核心要点：

  • 基本思想：

    • 将幂次分解为2的幂次
    • 预处理所有2^j次的幂
    • 时间复杂度从O(n)降低到O(log n)

  • 关键技巧：

    • 二进制拆分
    • 位运算优化
    • 处理模运算避免溢出
    • 处理特殊情况（n=0）

  • 常见应用：

    • 大数幂运算
    • 模幂运算
    • 矩阵快速幂
    • 斐波那契数列求解

实践建议：

  1. 编码前：

    • 确认问题是否适合用快速幂
    • 明确是否需要模运算
    • 检查指数范围

  2. 编码时：

    • 正确初始化result为1
    • 注意位运算的正确使用
    • 处理好模运算
    • 注意边界条件

  3. 调试时：

    • 验证小样本的正确性
    • 检查溢出问题
    • 测试特殊情况
    • 确认结果正确性
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心

6.2 进阶方向

倍增法的扩展：

  1. ST表（稀疏表）：

    • 解决区间最值查询(RMQ)
    • 预处理O(n log n)，查询O(1)
    • 适用于静态数组的区间查询

  2. 树上倍增：

    • 最近公共祖先(LCA)查询
    • 树上路径问题
    • 预处理O(n log n)，查询O(log n)

  3. 倍增与其他算法结合：

    • 倍增 + 动态规划
    • 倍增 + 贪心算法
    • 倍增 + 线段树

  4. 高级应用：

    • 快速数论变换
    • 多项式快速幂
    • 组合数学中的应用

实际应用中的注意事项：

  1. 在使用快速幂之前，先考虑：

    • 指数的大小范围
    • 是否需要模运算
    • 是否有负指数的情况

  2. 优化建议：

    • 使用位运算代替乘除
    • 预处理常用的幂次
    • 考虑内存局部性
    • 结合问题特性优化

  3. 记住：

    • 快速幂是倍增思想的基础应用
    • 理解二进制拆分是关键
    • 实践是掌握快速幂的最佳途径
    • 掌握快速幂为学习ST表和LCA打基础
返回目录 信息学 C++倍增法基础——快速幂 魅客科创中心
C++倍增法基础——快速幂

#c

演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调倍增法是算法设计中的进阶技巧，在竞赛和实际应用中都非常重要 - 可以简单提及本课程将重点讲解快速幂和倍增法的基础思想

目录页： - 简要介绍本次讲座的结构和内容安排 - 可以提及讲座的逻辑流程：从基础概念到快速幂实现，再到应用实例 - 强调我们将通过多个例子来深入理解快速幂的应用 - 提醒学生关注每个部分之间的联系，以及如何将理论应用到实践中

转场页： - 这是一个简单的转场页，用于引入倍增法概述部分 - 可以简单提及倍增法是算法设计中的重要策略，有着广泛的应用

倍增法概述： - 介绍倍增法的基本概念和核心思想 - 强调倍增法的高效性和应用场景 - 简要提及倍增法的历史和发展

倍增法的历史与应用： - 介绍倍增法的历史背景 - 讨论倍增法在不同领域的应用 - 强调倍增法的重要性和普遍性

转场页： - 引入倍增法的特点部分 - 可以简单提及理解这些特点有助于更好地应用倍增法

倍增法的特点： - 详细介绍倍增法的主要特点 - 强调这些特点如何帮助识别和解决倍增法问题 - 解释倍增法的优势和局限性

倍增法的优势与局限性： - 分析倍增法的优势和局限性 - 讨论何时应该选择倍增法 - 提供一些优化倍增法的思路

倍增法的适用场景： - 详细介绍倍增法适用的各种场景 - 提供一些实际应用的例子 - 讨论如何识别可以使用倍增法的问题

转场页： - 引入快速幂模板代码部分 - 可以简单提及掌握这些模板有助于快速实现快速幂算法

快速幂模板： - 提供快速幂的基本代码模板 - 解释模板中的关键部分 - 强调二进制拆分的思想

模幂运算模板： - 提供模幂运算的代码模板 - 解释与基本快速幂的区别 - 强调处理溢出的技巧

快速乘模板： - 提供快速乘的基本代码模板 - 解释如何避免大数乘法溢出 - 强调在模运算中的应用

倍增法的常见错误与注意事项： - 列举快速幂实现中的常见错误 - 提供避免这些错误的方法 - 强调细节的重要性

转场页： - 引入快速幂实例分析部分 - 可以简单提及我们将通过几个经典例子来深入理解快速幂

快速幂计算： - 详细介绍快速幂的实现和应用 - 通过具体例子说明快速幂的计算过程 - 强调快速幂的效率和适用条件

快速幂计算过程： - 提供快速幂计算的详细步骤 - 通过具体例子展示计算过程 - 分析算法的时间和空间复杂度