给定数字N和数组A。检查N是否可以表示为一个或多个数组元素的乘积

Question

给定一个数字N (where N <= 10^18)和一个数组A(consisting of at most 20 elements)。我必须告诉是否可以N通过乘以数组的某些元素来形成。请注意，我可以多次使用任何元素。

示例：N = 8和A = {2, 3}。在这里，8 = 2 * 2 * 2。所以答案是YES。但是，如果N = 15，则我无法将15用作一个或多个元素多次使用它们的乘积。因此，在这种情况下，答案是NO。

我该如何解决这个问题？

Answer 1

简单的伪代码：

A_divisors = set()
for x in A:
    if num % x == 0:
        A_divisors.add(x)

candidates = A_divisors.clone()
seen = set()

while(candidates.size()):
    size = divisors.size()
    new_candidates = set()
    for y in candidates:
        for x in A_divisors:
            if num % (x * y) == 0 and (x * y) not in seen:
                new_candidates.add(x * y)
                seen.add(x * y)
            if x * y == num:
                return true
    candidates = new_candidates

return false

复杂度：O（| A | * k * log k），其中k为除数。日志k将是添加和检查元素是否存在于集合中的成本。使用基于哈希的方法，它将是O（1）并可以删除。我还假设％，*运算为O（1）。