C++区间幂数查询实现：代码逻辑疑问及更优解法咨询

问题1解答 #

自定义Power函数的作用是判断输入的number是不是base的整数次幂，符合条件就返回对应指数，否则返回0。

• 用log计算是利用对数换底公式：数学上，以base为底number的对数等于ln(number)/ln(base)，如果number刚好是base的n次方，这个计算结果理论上等于整数n。
• 加0.5是为了修正浮点数计算的精度误差：log计算结果是浮点数，比如本来理论值是6，可能因为运算精度问题得到5.999999999或者6.000000001，加0.5之后再转int（C++中int转换会截断小数部分），就相当于做了四舍五入，能拿到正确的整数值。
• 最后用pow(base, power) == number做校验，就是怕浮点数误差导致算出的指数不对，只有验证通过才返回指数，否则返回0。

问题2解答 #

肯定会漏判，完全不能覆盖所有场景。
题目中b的上限是1000000，仅平方数的底数最大就可以到1000（因为1000²=1000000），现在代码只遍历底数2到10，那11²=121、12²=144……999²=998001这些符合要求的幂数都会被漏掉，更别说底数大于10的更高次幂了。

问题3解答 #

有更简单高效的实现方法，还能避免浮点数精度问题：
1000000范围内最大的指数是19（2^{19=524288，2}20=1048576超过1000000），我们可以从最高指数往最低指数遍历（这样第一次记录到的数就是指数最大的形式，符合题目要求）：

• 先开一个长度1000001的数组，用来记录每个数对应的底数，初始全部标记为未找到。
• 指数n从19遍历到2：
  • 底数x从2开始，循环用整数乘法计算x的n次方，一旦结果超过1000000就停止当前指数的遍历。
  • 如果计算出的幂数还没被标记过，就把它的底数记录下来，后续低指数遍历到同一个数的时候不需要修改，保证保留最大指数的形式。
• 最后遍历区间[a,b]，把有记录的数按要求的格式输出即可。

内容的提问来源于stack exchange，提问作者user10203585