Дано число K и набор отсортированных чисел. Найти, есть ли в наборе число, которое делит

Question

Дано число k и набор отсортированных чисел. Найдите, есть ли какое-либо число в наборе, которое делит это число.

Например, если k = 8 и установлено { 3, 4, 5}, 4 разделит 8. 4 - это ответ.

В худшем случае решение O(n).

Можем ли мы сделать это лучше?

Answer 1

Как насчет факторизации числа (8 дает нам 4 2 1), а затем искать факторы в вашем заданном наборе? Вы можете использовать набор пересечений или разделить пополам поиск вашего списка факторов. Я думаю, что это даст вам более быстрый ответ для больших наборов.

Answer 2

Рассчитайте gcd of k и произведение членов множества. Например, gcd(3*4*5,8) = 4.

Answer 3

Если k простое, у него нет множителей в множестве, и все готово. В противном случае k = p*q, где p - наименьший коэффициент k. Сделайте двоичный поиск для q. Если найдено, вы сделали. В противном случае рефакторинг k = p '* q', где p '- следующий по величине коэффициент k после p - если его нет, все готово. В противном случае продолжите двоичный поиск q '- обратите внимание, что q'

РЕДАКТИРОВАТЬ: Хммм... Я думаю, это не O(logn). Если, например, список содержит f-1 для каждого фактора f из k, то вам придется искать каждый f последовательно, нажимая f-1 каждый раз... это будет O(n).