Дано число 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).

Answer 2

Вы можете следовать нижеприведенному подходу:

1. Формы 2 очереди: Q2 и Q3.
2. Добавить 2 в Q2 и 3 в Q3.
3. Получите минимум заголовка обеих очередей, скажем, h. Удалить h из соответствующей очереди. Проверьте, равно ли оно числу N. Если да, верните истину. Если оно больше N, вернуть false.
4. Если оно меньше N, то добавьте 2*h в Q2 и 3*h в Q3. Повторите шаги с 3 по 4.

Обратите внимание, что когда минимальное значение h составляет от Q3, вам не нужно добавлять 2*h в Q2. Это потому, что вы уже добавили этот элемент в Q3 раньше. (Я оставлю это на ваше усмотрение}. Продолжайте эту процедуру, пока ваш h не станет больше чем N.

Если у вас есть больше таких номеров, вы также можете создавать там очереди. Я думаю, что это оптимальное решение, если вам нужно обработать больше чисел.

Можете ли вы угадать временную и пространственную сложность этого?

Answer 3

Поскольку вы не показываете код или алгоритм, я просто дам одну идею. Если вам нужна дополнительная помощь, пожалуйста, покажите больше своей работы над этой проблемой.

Обратите внимание, что N может иметь длину не более 60 бит. Это достаточно мало, чтобы N можно было довольно быстро разложить на основные факторы. Поэтому сначала разработайте хороший алгоритм факторинга для чисел такого размера.

Ваш алгоритм будет учитывать N и каждый из элементов в вашем массиве A. Если есть какой-либо простой множитель N, который не делится ни на один элемент A, тогда ваш ответ NO. Так обстоит дело в вашем примере N = 15.

Теперь вы работаете с простыми множителями и их показателями в N и в элементах A. Теперь вы хотите найти подмножество (или, точнее, подмножество) в A, где показатели для каждого простого числа складываются с этим в N. Это значительно уменьшает размеры ваших номеров и облегчает задачу.

Эта последняя часть не тривиальна. Больше работайте над этой проблемой и покажите нам часть своей работы, тогда мы продолжим помогать вам.