algorithm - 求一个数与一个数的最小绝对差，形式为 b^x，其中 b,x > 1

Question

考虑一个例子 70其中最接近的数字是64即2^6 .所以最小绝对差是6 .
什么是解决此类问题的好方法(lg n 时间复杂度)？
编辑:b和 x是 integers
编辑:1 < n < 10^9其中 n是必须找到其最小绝对差的数字。假设 q查询即将到来 1 < q < 10^5

Answer 1

对于所有合理的 k 值，您可以找到数字的第 k 个根，向上和向下舍入，并找到最接近 n 的值。

一旦 n 的第 k 个根小于 2，您就可以停止该算法，这意味着要找到 O(log n) 个根。

下面是一些实现它的 Python 代码:

import math

def nearest_pow(n):
    if n <= 1:
        return n
    best = n
    for k in xrange(2, n):
        p = math.pow(n, 1.0 / k)
        for x in xrange(2):
            best = min(best, abs((int(p) + x) ** k - n))
        if int(p) == 1:
            break
    return best

print nearest_pow(70)

终止条件 int(pow(n, 1/k)) == 1 发生在 k 至多为 lg(n)+1 时，所以这个算法是 O(log n)，假设 math.pow 是 O(1)。