练习·快速幂有多快

单选题　难度 3

算 a 的 1000000000 次方，朴素乘法要 10 亿次，快速幂呢？

题目

快速幂计算 a^b 所需的乘法次数量级是？

1. log b
2. b
3. b/2
4. √b

知识点讲解

快速幂每轮指数折半，乘法次数约 log₂b 次——10 亿次方也只要 30 次左右。