快速幂(模幂运算)
二进制分治优化幂运算,搭配取模防止大数溢出,广泛用于密码算法
步骤: 0 结果: - 状态: 就绪
算法说明
时间复杂度:O(log n)
空间复杂度:O(1)
核心思想:将指数按二进制拆分,通过反复平方将幂运算从 O(n) 降至 O(log n)。每一步检查当前二进制位:为1则累乘到结果,然后底数平方。配合取模运算防止大数溢出。
二进制分治优化幂运算,搭配取模防止大数溢出,广泛用于密码算法
时间复杂度:O(log n)
空间复杂度:O(1)
核心思想:将指数按二进制拆分,通过反复平方将幂运算从 O(n) 降至 O(log n)。每一步检查当前二进制位:为1则累乘到结果,然后底数平方。配合取模运算防止大数溢出。