Нахождение размера наименьшего подмножества с GCD = 1

10

Это проблема с практической сессии Польского студенческого соревнования по программированию 2012 года . Хотя я мог найти решения для основного конкурса, я не могу найти решение этой проблемы где-либо.

Проблема в том, что: учитывая набор из различных положительных целых чисел, не превышающих , найдите размер наименьшего подмножества, у которого нет общего делителя, кроме 1. не более 500, и можно предположить, что решение существует ,10 9 m NN109mN

Мне удалось показать, что . Я рассуждаю так: предположим, что существует минимальное подмножество размера с gcd = 1. Тогда все 9-подмножеств должны иметь gcd> 1. Таких подмножеств ровно 10, и их gcds должны быть попарно взаимно просты. Пусть эти gcds будут , где , для i \ neq j . Тогда максимальное число в S равно g_2g_3 ... g_ {10} . Но g_2g_3 ... g_ {10} \ ge 3 \ times5 \ times7 \ times11 \ times ... \ times29 = 3234846615> 10 ^ 9 , противоречие.m9S|S|=10S1<g1<g2<...<g10gcd(gi,gj)=1ijSg2g3...g10g2g3...g103×5×7×11×...×29=3234846615>109

Однако даже при этом прямая грубая сила все еще слишком медленная. У кого-нибудь есть другие идеи?

Wakaka
источник
Почему не может g2=2 ?
vonbrand
g2>g12 . g1 не может быть 1, поскольку 9-подмножества не могут иметь gcd 1.
Вакака

Ответы:

1

Эта проблема эквивалентна следующей, и тривиально сконструировать сокращение в обоих направлениях.

Учитывая список битовых векторов, найдите их минимальное количество, чтобы andвсе они приводили к битному вектору. 0()

Затем мы покажем, что набор обложек уменьшается до . Под набором покрытий я подразумеваю заданный список наборов , найти минимальное количество наборов, которое охватывает их объединение.()S1,,Sk

Мы упорядочиваем элементы в наборах как . Пусть , где если , 0 в противном случае. Обратите внимание, что эта функция является биекцией, поэтому она имеет обратную.a1,,anf(S)=(1χa1(S),,1χan(S))χx(S)=1xS

Теперь, если мы решим для , и решения будут , тогда - решение для укрытия.()f(S1),,f(Sk){f(Sb1),,f(Sbm)}{f1(Sb1),,f1(Sbm)}

Таким образом, я думаю, что эта проблема проверяет способность обрезать пространство поиска.

Чао Сюй
источник
Как вы находите минимальное покрытие вершин?
Ювал Фильмус
о нвм это решение, вместо этого установлено покрытие.
Chao Xu
1
Это правда, но я думаю, что мы можем использовать некоторые свойства этого особого случая. Например, в этом случае все наборы очень большие, с размерами не менее . На самом деле, если бы числа в наборах были маленькими, их размеры были бы еще больше. Кроме того, мы определенно можем найти 9 комплектов, которые охватывают все. В любом случае, как вы предлагаете мне обрезать пространство поиска? n9
Вакака
Я не понимаю, как проблема (*) эквивалентна той, которая приведена в вопросе. Во-первых, проблема, приведенная в этом вопросе, обещает, что все целые числа будут , что соответствует гарантии о весах битовых векторов, которая не появляется в задаче (*). 109
DW
1

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

Я объясню алгоритм более подробно ниже, но сначала он помогает определить бинарный оператор . Если - наборы натуральных чисел, определитеS,T

ST={gcd(s,t):sS,tT}.

Обратите внимание, чтои (в вашей задаче); обычно будет даже меньше, чем предполагает любая из этих границ, что помогает сделать алгоритм эффективным. Также обратите внимание, что мы можем вычислить с помощьюОперации gcd простым перечислением.|ST||S|×|T||ST|109STST|S|×|T|

С этим обозначением вот алгоритм. Пусть будет входным набором чисел. Вычислить , затем , затем и так далее. Найдите наименьшее такое, что но . Тогда вы знаете, что размер наименьшего такого подмножества равен . Если вы также хотите вывести конкретный пример такого подмножества, сохраняя обратные указатели, вы можете легко восстановить такой набор.S1S2=S1S1S3=S1S2S4=S1S3k1Sk1Sk1k

Это будет относительно эффективно, так как ни один из промежуточных наборов не увеличится в размерах выше (на самом деле их размер, вероятно, будет намного меньше этого размера), а время выполнения требует около операции gcd.109500×(|S1|+|S2|+)

Вот оптимизация, которая может повысить эффективность еще больше. В принципе, вы можете использовать повторное удвоение, чтобы найти наименьшее такое, что . В частности, для каждого элемента мы отслеживаем наименьшее подмножество чей gcd ​​равен а размер равен . (Когда вы удаляете дубликаты, вы разрешаете связи в пользу меньшего подмножества.) Теперь вместо того, чтобы вычислять последовательность из девяти наборов , мы вместо этого вычисляем последовательность из пяти наборов , вычисляя , затем , затемk1SkxSiS1xiS1,S2,S3,S4,,S9S1,S2,S4,S8,S9S2=S1S1S4=S2S2S8=S4S4 , затем . На ходу найдите первый такой, что . Как только вы нашли такое, что , вы можете немедленно остановиться: вы можете найти наименьшее подмножество, чей gcd ​​равен , посмотрев на подмножество, связанное с . Таким образом, вы можете остановиться, как только достигнете набора такого, что , что позволяет останавливаться раньше, если вы найдете меньшее подмножество.S9=S1×S8k[1,2,4,8,9]1Skk1Sk11Sk1Sk

Это должно быть эффективным с точки зрения времени и пространства. Чтобы сэкономить место, для каждого элемента вам не нужно хранить весь набор: достаточно сохранить два обратных указателя (поэтому два элемента , из которых вы взяли gcd, чтобы получить ) и необязательно размер соответствующего подмножества.xSkSi,Sjx

В принципе, вы можете заменить последовательность на любую другую цепочку добавления . Я не знаю, будет ли какая-то другая цепочка дополнений лучше. Оптимальный выбор может зависеть от распределения правильных ответов и ожидаемых размеров наборов , что мне не ясно, но, вероятно, может быть получено опытным путем с помощью экспериментов.[1,2,4,8,9]Sk

Благодарности: Моя благодарность KWillets за идею сохранения подмножества чисел вместе с каждым элементом , что позволяет рано останавливаться.Si

DW
источник
Я считаю, что бинарный поиск не нужен; Вы можете хранить количество элементов для каждого gcd и устанавливать минимальную сумму пары при каждом удвоении.
KWillets
Отличный момент, @KWillets! Спасибо за эту прекрасную идею! Я включил это в свой ответ.
DW
0

Возможно, это быстрее, если взглянуть на это по-другому ... наибольшее простое число, меньше равно 31607, для общего числа 3401 простых чисел от 2 до 31607, что не очень большое число. Напишите каждое из чисел, которое вам дано, с полным множителем над простыми числами до 31607: Здесь - 1 или большое простое число. Тогда набор относительно прост, если соответствующие векторы линейно независимы (а их s разные или оба равны 1), и вы ищете ранг матрицы.109

ai=p1ni1p2ni2Pi
PiainijP
vonbrand
источник
Какая связь с линейной независимостью? Векторы и линейно независимы, но GCD равен то время как мы хотим . (1,1)(1,0)(1,0)(0,0)
Юваль Фильмус
1
Кажется, линейная независимость не работает, но мы можем использовать это простое разложение по-другому. Для каждого простого числа (среди и не более ) определите набор как совокупность всех чисел (среди данного набора), для которых не имеет множителя. Теперь проблема состоит в том, чтобы найти наименьшее подмножество чисел, такое, что для каждого , . Это проблема заданного множества, эквивалентная задаче накрытия множеств. Это полная, но может быть несколько реализаций, достаточно быстрых для этого размера. p3401 pi500 PiAppBAp|ApB|1NP
Polkjh
Не могли бы вы указать мне некоторые реализации, которые могли бы работать? Пока что я могу найти только приближенные алгоритмы. Спасибо!
Вакака
В этом обзоре рассматриваются как приблизительные, так и точные решения. А при ответе на комментарий, пожалуйста, добавьте @ имя-человека в комментарий. Он отправит уведомление этому человеку. В противном случае они могут даже не узнать о вашем комментарии.
Polkjh
-1

Если вы можете найти подмножество с gcd (S) = 1, то я всегда могу удалить избыточные элементы из подмножества, пока не останется только 2 элемента, которые имеют gcd (S) = 1. Поэтому я могу утверждать, что либо наименьшее Подмножество будет содержать 2 элемента или не будет существовать.

Теперь мы используем рекурсию для решения этой проблемы. Давайте разделим массив чисел на 2 части, одну с n-1 элементами и одну с 1 элементом (последний элемент). Либо 2 числа будут в первых n-1 элементах, либо один элемент будет в 1-й части в паре с последним элементом. Поэтому мы можем решить эту проблему в

T (n) = T (n-1) + O (n) время. что означает T (n) = O (n ^ 2).

Pratik
источник
4
gcd(6,10,15)=1 . Какой элемент вы можете удалить?
Рик Декер