我正在准备面试，遇到了这个问题:
我想到了日志和东西，但不能确定如何检查数字是否为表格。你们中的任何一个都可以帮忙吗？ :)
最佳答案
要走“拿日志和东西”的路。请注意，对于整数a和b> log_2(N)，N> 1永远不会是a ^ b。因此，您可以检查2和log_2(N)之间的每个整数b的floor(N ^(1/b))^ b = N。您必须处理log(N)个指数，每个指数最多产生一个N的数字。
这比@dasblinkenlight的解决方案要快得多，后者需要首先将N分解为因数。 (没有整数倍分解的多项式时间算法，即N位数的多项式。但是，可以在多项式时间内完成具有小指数的整数幂运算。)