快速幂算法（模重复平方法） 快速幂算法是一种用于高效计算大整数幂的算法，特别适用于模幂运算（如计算a^b mod m）。其时间复杂度从朴素算法的O(b)优化到O(log b)。 问题描述 给定底数a、指数b和模数m（可选），计算a^b或a^b mod m。其中a、b、m可能都是很大的整数（如b可达10^9），要求高效计算。 算法原理 快速幂基于幂的二进制表示和分治思想。核心观察是指数b可以表示为二进制数，从而将a^b分解为多个a的2的幂次方的乘积。 解题步骤 初始化结果 ：将结果变量res初始化为1（因为任何数的0次幂为1）。 循环处理指数的每一位 ：当指数b大于0时循环： 检查最低位 ：如果b的二进制表示的最低位为1（即b为奇数），则将当前底数a乘到结果res中。 底数平方 ：将底数a平方（即计算a^2），为处理下一位做准备。 指数右移 ：将指数b右移一位（相当于b除以2并向下取整），处理下一个二进制位。 返回结果 ：循环结束后，res即为a^b的结果。 带模运算的扩展 当需要计算a^b mod m时，只需在每一步乘法后立即取模，防止数值溢出： res = (res * a) % m a = (a * a) % m 示例演示 计算3^13（a=3, b=13）： b=13（二进制1101）为奇数 → res=1* 3=3, a=3^2=9, b=6 b=6（二进制110）为偶数 → res不变, a=9^2=81, b=3 b=3（二进制11）为奇数 → res=3* 81=243, a=81^2=6561, b=1 b=1（二进制1）为奇数 → res=243* 6561=1594323, a=6561^2, b=0 结果：3^13=1594323 复杂度分析 时间复杂度：O(log b)，因为指数b每次减半 空间复杂度：O(1)，仅需常数额外空间 应用场景 密码学中的模幂运算（如RSA加密） 大数计算中的幂运算 算法竞赛中的高效计算需求 该算法通过二进制分解将线性计算优化为对数级，是处理大数幂运算的标准方法。