快速幂(模幂运算)

二进制分治优化幂运算,搭配取模防止大数溢出,广泛用于密码算法

步骤: 0 结果: - 状态: 就绪

算法说明

时间复杂度:O(log n)

空间复杂度:O(1)

核心思想:将指数按二进制拆分,通过反复平方将幂运算从 O(n) 降至 O(log n)。每一步检查当前二进制位:为1则累乘到结果,然后底数平方。配合取模运算防止大数溢出。

核心代码