Нахождение всех комбинаций элементов из двух наборов так, чтобы их геометрическое среднее попало в третий набор
У меня есть целые числа от 1 до n, Я случайным образом выделяю каждое целое число в один из трех наборов A, B а также C (A ∩ B = B ∩ C = C ∩ A = Ø). Каждое целое число принадлежит одному набору. Поэтому мне нужно рассчитать все комбинации элементов (a,b) такой, что a ∈ A, b ∈ Bи среднее геометрическое a,b принадлежит C, В принципе sqrt(a*b) ∈ C,
Мое решение состоит в том, чтобы сначала пометить массив размера n входил ли каждый элемент в набор A,B или C. Затем я перебираю массив для всех элементов, которые принадлежат A, Когда я сталкиваюсь с одним, я снова перебираю все элементы, которые принадлежат B, Если array[sqrt(a*b)] == Cпотом добавляю (a, b, sqrt(a,b)) как одна из возможных комбинаций. Затем я делаю то же самое для всего массива, который O(n^2),
Возможно ли более оптимальное решение?
1 ответ
Это можно сделать с большей сложностью, чем O(n^2). Схематичное решение находится в O(n * sqrt(n) * log(n)).
Основная идея заключается в следующем:
- пусть (a, b, c) будет хорошим решением, то есть с sqrt(a * b) = c. Мы можем записать a как a = s * t^2, где s - произведение простых чисел, имеющих нечетные показатели в факторизации простого числа. Гарантируется, что оставшаяся часть является идеальным квадратом. Поскольку a * b - идеальный квадрат, то b должно иметь форму s * k^2. Для каждого a (существует O(n) таких чисел), после нахождения s из разложения выше (это можно сделать в O(log(n)), как это будет описано далее), мы можем ограничить наш поиск число b к числам вида b = s * k^2, но есть только O(sqrt(n)) числа, подобные этому, меньше чем n. Для каждой пары a, b, перечисленной таким образом, мы можем проверить в O(1), существует ли хороший c, используя представление, которое вы использовали в вопросе.
Одна критическая часть в идее выше - это разложение a на s * t ^ 2, то есть нахождение простых чисел, которые имеют нечетную степень в факторизации a.
Это можно сделать, используя этап предварительной обработки, который находит главные факторы (но не также их мощности) каждого числа в {1, 2, .. n}, используя слегка модифицированное сито Эратосфена. Эта измененная версия не только пометит число как "не простое" при итерации по кратным простого числа, но также добавит текущее простое число к списку факторов текущего кратного числа. Временная сложность этого этапа предварительной обработки составляет n * sum{для каждого простого p
Используя результат предварительной обработки, который представляет собой список простых чисел, которые делят a, мы можем найти эти простые числа с нечетной степенью в O(log(n)). Это достигается путем деления a на каждое простое число в списке, пока оно не станет более делимым на это простое число. Если мы сделали нечетное число делений, то используем текущее простое число в s. После того, как все деления выполнены, результат будет равен 1. Сложность этого равна O(log(n)), потому что в худшем случае мы всегда делим начальное число на 2 (наименьшее простое число), поэтому потребуется не более log2(a) шагов для достижения значения 1.
Сложность основного шага доминирует над сложностью предварительной обработки, поэтому общая сложность этого подхода составляет O(n * sqrt(n) * log(n)).
Примечание: в разложении a = s * t ^ 2 s является произведением простых чисел в a с нечетными показателями, но их показатель степени не используется в s (т.е. s является просто произведением этих простых чисел с показателем 1), Только в этой ситуации гарантируется, что b должно иметь форму s * k^2. В самом деле, поскольку a * b = c * c, простая факторизация правой части использует только четные показатели, поэтому все простые числа из s также должны появляться в b с нечетными показателями, а все другие простые числа из факторизации b должны иметь четные экспонент.
Расширяя следующую строку: "мы можем ограничить наш поиск числа b теми, которые имеют вид b = s * k ^ 2, но есть только O(sqrt(n)) чисел, подобных этому меньше n".
Давайте рассмотрим пример. Представьте, что у нас есть что-то вроде n = 10000, и в настоящее время мы ищем решения, имеющие a = 360 = 2 ^ 3 * 3 ^ 2 * 5. Простые числа с нечетным показателем в факторизации a равны 2 и 5 (таким образом, s = 2 * 5; а = 10 * 6^2).
Поскольку a * b является идеальным квадратом, это означает, что все простые числа в простой факторизации a * b имеют четные показатели. Это означает, что эти два простых числа (2 и 5) также должны появляться в факторизации b с нечетными показателями, а остальные показатели в простой факторизации b должны быть четными. Таким образом, b имеет вид s * k ^ 2 = 10 * k ^ 2.
Итак, мы доказали, что b = 10 * k ^ 2. Это полезно, потому что теперь мы можем быстро перечислить все значения b этой формы (в O(sqrt(n))). Нам нужно только рассмотреть k = 1, k = 2,..., k = (int) sqrt (n / 10). Большие значения k приводят к значениям b, превышающим n. Каждое из этих значений k определяет одно значение b, которое нам необходимо проверить. Обратите внимание, что когда проверяя одно из этих значений b, следует сначала проверить, действительно ли оно находится в множестве B, что можно сделать в O(1), и есть ли sqrt (a * b) в множестве C, что также можно сделать в O(1).