求一个数字的最小绝对差值,其形式为b ^ x,其中b,x> 1

Question

考虑一个70最接近的数字是64ie 的例子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).