快速幂
入门快速幂是模运算和大数计算的基础工具。
// 算法讲解
快速幂
演示快速幂计算 a^b mod m 的过程。
待机
速度 中
待机 ⌨1long long fastPow(long long base, long long exp, long long mod) {
2 long long result = 1;
3 while (exp > 0) {
4 if (exp & 1) result = result * base % mod;
5 base = base * base % mod;
6 exp >>= 1;
7 }
8 return result;
9}
复杂度分析
时间 O(log b)
空间 O(1)
最优 O(1)
最坏 O(log b)
算法讲解
快速幂的核心思想：将指数 b 用二进制表示，每轮将底数平方，指数右移一位。
当指数当前位为 1 时，将当前底数乘入结果。
时间复杂度 O(log b)，空间复杂度 O(1)。
常用于模运算、矩阵快速幂、大数计算等场景。