algorithm - 判断一个数是否满足欠定方程

Question

理论上是否可能以 O(1) 的空间和时间复杂度来决定一个已知的正整数 K 是否是方程的解

其中 a 和 b 是固定的正整数(不是对方的倍数)，μ_i 是未知 非负整数，除了有限数量的(但不是全部)都是零？如果在 O(1) 空间和时间上不可能，那么最知名的算法对空间和时间的要求是多少？

我发现解决这个问题的唯一方法是提前枚举所有可能的K‌的子集，但这当然需要我选择上限M 和 N 使得 i ≤ N 和∀ μ_i ≤ M。更糟糕的是，它的空间需求是 O(M^N)，这可能是如此之大以至于没有查找算法在真实硬件上达到 O(1) 检索性能。我有一种不好的预感，这实际上是 Knapsack Problem伪装，但我还没有足够的把握放弃。

我试图在空间和时间上都达到 O(1)，因为我需要知道这是否可以在 CPU 或 RAM 几乎没有余量的嵌入式环境中实时完成。

我不需要知道一组令人满意的 μ_i 值。

编辑: 这个 Python 函数计算一个集合对象 S 使得 K in S 为真当且仅当 K 是上述等式的解之一，给定 a、b 和截止点 M 和 N 如上所述。

def compute_set(a, b, M, N):
    ss = [a*i + b for i in xrange(1,N+1)]
    aa = itertools.product(xrange(0,M+1), repeat=N)
    rv = set(map(lambda a: sum(a[i]*ss[i] for i in xrange(N)), aa))
    rv.remove(0)
    return rv

Answer 1

分两个阶段求解。

在第 1 阶段，使用处理 Diophantine equations 的标准技术计算集合 {(x, y): x, y in Z and ax + by = K} 的描述.让 g = gcd(a, b);除非 g 除 K，否则没有解决方案。通过 extended Euclidean algorithm 计算 g求解 ax' + by' = g 以及计算 g；第一个解是 (x', y') * K/g。其他解与 (-b/g, a/g) 的整数倍相加。

在第 2 阶段，计算可以通过 µ_i 的不同选择实现的 (x, y) 解的描述。由于 K ≥ 0 我们知道 y ≥ 1 是必要条件。如果 n 是一个变量，那么 x ≥ 0 和 y ≥ 1 是充分必要条件(设置 µ₀ = y - 1 和 µ_x = 1 和所有其他微秒到 0)。

如果 n 是一个参数，那么事情就有点棘手了。使用阶段 1 的结果，找到 x ≥ 0 且 y 最大值的解 (x, y)(如果没有这样的解，则 K 不可行)。对于这个解决方案，检查是否 x/y ≤ n。

def egcd(A, B):
    """Returns a triple (gcd(A, B), s, t) such that s * A + t * B == gcd(A, B)."""
    a, b, s, t, u, v = A, B, 1, 0, 0, 1
    while True:
        assert s * A + t * B == a
        assert u * A + v * B == b
        if not b:
            break
        q, r = divmod(a, b)
        a, b, s, t, u, v = b, r, u, v, s - q * u, t - q * v
    return a, s, t

def solvable(K, a, b):
    g, s, t = egcd(a, b)
    q, r = divmod(K, g)
    if r:
        return False
    x, y = s * q, t * q
    assert a * x + b * y == K
    d = a // g
    q, r = divmod(y, d)
    if r <= 0:
        q -= 1
        r += d
    assert 0 < r <= d
    x, y = x + q * (b // g), r
    assert a * x + b * y == K
    return x >= y