Дано число k и набор отсортированных чисел.Найдите, есть ли какое-либо число в наборе, которое делит это число.
Например, если k = 8, и набор равен {3, 4, 5}, 4 разделит 8. 4 - ответ.
В худшем случае решение O (n).
Можем ли мы сделать это лучше?
Как насчет факторизации числа (8 дает нам 4 2 1), а затем искать факторы в вашем заданном наборе? Вы можете использовать набор пересечений или разделить пополам поиск вашего списка факторов. Я думаю, что это даст вам более быстрый ответ для больших сетов.
Рассчитайте gcd для k и произведение членов множества.Например, gcd (3 * 4 * 5,8) = 4.
Если k простое, в наборе нет факторов, и все готово. В противном случае k = p * q, где p - наименьший коэффициент k. Сделайте двоичный поиск для q. Если найден, все готово. В противном случае рефакторинг k = p '* q', где p '- следующий по величине коэффициент k после p - если его нет, все готово. В противном случае продолжите двоичный поиск q '- обратите внимание, что q' EDIT: Хммм ... Я думаю, это не O (logn). Если, например, список содержит f-1 для каждого фактора f из k, то вам придется искать каждый f подряд, каждый раз нажимая f-1 ... это будет O (n).
EDIT: Хммм ... Я думаю, это не O (logn). Если, например, список содержит f-1 для каждого фактора f из k, то вам придется искать каждый f подряд, каждый раз нажимая f-1 ... это будет O (n).