快速幂:浮点数 n 次方与 A^B 取模
哪些公司问过
答案要点
- 二进制拆分指数:最低位为 1 时乘入结果,底数自乘、指数右移,O(log n)
- 边界:n=0、n 为负数取倒数、int 最小值取反溢出需转 long、x=0
- 取模版本:底数先取模,每次乘法后取模,保证中间结果不溢出
- 模数为 10^7 时乘积最大约 10^14,64 位整数可容纳
- 模数更大时用 __int128 或龟速乘;指数极大时可用欧拉定理降幂
易错点
- n 为 int 最小值时直接取相反数溢出
- 取模版本只在最后取模,中间结果早已溢出
- 欧拉降幂时忽略底数与模数不互质的情况
面试官常见追问
- 从 A 和 B 两个方向怎么改进?
- 为什么快速幂是 O(log n)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。