Znalezienie rozmiaru najmniejszego podzbioru z GCD = 1

10

Jest to problem z sesji treningowej Polskiego Konkursu Programowania Uczelnianego 2012 . Chociaż mogłem znaleźć rozwiązania dla głównego konkursu, nie mogę nigdzie znaleźć rozwiązania tego problemu.

Problem polega na tym: biorąc pod uwagę zbiór $N$ wyraźnych liczb całkowitych dodatnich nie większych niż , znajdź rozmiar najmniejszego podzbioru, który nie ma wspólnego dzielnika innego niż 1. wynosi co najwyżej 500 i można założyć, że istnieje rozwiązanie . $10^9$ $m$ $N$

Udało mi się pokazać, że . Moje rozumowanie jest następujące: załóżmy, że istnieje minimalny podzbiór o rozmiarze , z gcd = 1. Wtedy wszystkie 9-podzbiorów musi mieć gcd> 1. Istnieje dokładnie 10 takich podzbiorów, a ich gcds muszą być parami coprime. Niech te gcds będą wynosić , gdzie , dla . Zatem maksymalna liczba w to . Ale , sprzeczność. $m \le 9$ $S$ $|S|=10$ $S$ $1 < g_1 < g_2 < ... < g_{10}$ $\gcd(g_i,g_j)=1$ $i \neq j$ $S$ $g_2g_3...g_{10}$ $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$

Jednak nawet przy tym bezpośrednia brutalna siła jest wciąż zbyt wolna. Czy ktoś ma jakieś inne pomysły?

algorithms number-theory

— Wakaka
źródło

Dlaczego nie może ?

g_{2} = 2

$g_2 = 2$

— vonbrand,

g_{2} > g_{1} \geq 2

$g_2 > g_1 \ge 2$ . nie może być 1, ponieważ 9 podzbiorów nie może mieć gcd 1.

g_{1}

$g_1$

— Wakaka

1

Ten problem jest równoważny z poniższym, a budowanie redukcji w obie strony jest banalne.

Biorąc pod uwagę listę wektorów bitowych, znajdź ich minimalną liczbę, tak aby andwszystkie uzyskały wektor bitów. $0$ $(*)$

Następnie pokazujemy, że zestaw ochrony zmniejsza się do . Przez zestaw okładek rozumiem, biorąc pod uwagę listę zestawów , znajdź minimalną liczbę zestawów, która pokrywa ich związek. $(*)$ $S_1,\ldots,S_k$

Zamawiamy elementy w zestawach na . Niech , gdzie jeśli , 0 w przeciwnym razie. Zauważ, że ta funkcja jest bijectcją, więc ma odwrotność. $a_1,\ldots,a_n$ $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$ $\chi_x(S) = 1$ $x\in S$

Teraz, jeśli rozwiążemy na , a rozwiązaniem jest , to to rozwiązanie zapewniające ochronę. $(*)$ $f(S_1),\ldots,f(S_k)$ $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$ $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$

Myślę więc, że ten problem polega na sprawdzeniu czyjejś umiejętności przycinania przestrzeni wyszukiwania.

— Chao Xu
źródło

Jak znaleźć minimalną osłonę wierzchołków?

— Yuval Filmus

oh nvm to rozwiązanie, zamiast tego ustawiono osłonę.

— Chao Xu

1

To prawda, ale myślę, że może uda nam się wykorzystać pewne właściwości tego szczególnego przypadku. Na przykład w tym przypadku zestawy są bardzo duże, a ich rozmiary nie są mniejsze niż

. W rzeczywistości, jeśli wszystkie liczby w zestawach są małe, ich rozmiary byłyby jeszcze większe. Ponadto zdecydowanie możemy znaleźć 9 zestawów, które obejmują wszystko. W każdym razie, jak sugerujesz przycinać przestrzeń wyszukiwania?

n - 9

$n-9$

— Wakaka

Nie rozumiem, jak problem (*) jest równoważny z podanym w pytaniu. Po pierwsze, problem podany w pytaniu ma obietnicę, że wszystkie liczby całkowite będą miały

, co odpowiada gwarancji dotyczącej wag wektorów bitowych, które nie występują w problemie (*).

\leq 10^{9}

$\le 10^9$

— DW

1

Jest to względnie wydajne rozwiązanie, obliczając wszystkie pary gcd, usuwając duplikaty, a następnie rekursując. To czynność polegająca na usuwaniu duplikatów przed ponownym użyciem sprawia, że jest to wydajne.

Wyjaśnię algorytm bardziej szczegółowo poniżej, ale najpierw pomaga zdefiniować operator binarny . Jeśli są zestawami liczb całkowitych dodatnich, zdefiniuj $\otimes$ $S,T$

S \otimes T = {gcd (s, t) : s \in S, t \in T} .

$S \otimes T = \{\gcd(s,t) : s \in S, t \in T\}.$

Zauważ, że i (w twoim problemie); zazwyczaj będzie nawet mniejszy niż sugeruje jedna z tych granic, co pomaga zwiększyć efektywność algorytmu. Zauważ też, że możemy obliczyć pomocą operacje gcd przez proste wyliczenie. $|S \otimes T| \le |S| \times |T|$ $|S \otimes T| \le 10^9$ $S \otimes T$ $S \otimes T$ $|S| \times |T|$

Przy tej notacji oto algorytm. Niech będzie wejściowym zestawem liczb. Oblicz , następnie , następnie i tak dalej. Znajdź najmniejszy taki, że ale . Wtedy wiesz, że rozmiar najmniejszego takiego podzbioru wynosi $S_1$ $S_2 = S_1 \otimes S_1$ $S_3 = S_1 \otimes S_2$ $S_4 = S_1 \otimes S_3$ $k$ $1 \in S_k$ $1 \notin S_{k-1}$ $k$ . Jeśli chcesz również przedstawić konkretny przykład takiego podzbioru, zachowując wskaźniki wsteczne, możesz łatwo zrekonstruować taki zestaw.

Będzie to stosunkowo wydajne, ponieważ żaden z zestawów pośrednich nie wzrośnie powyżej (w rzeczywistości ich rozmiar prawdopodobnie będzie znacznie mniejszy niż ten), a czas działania wymaga około operacje gcd. $10^9$ $500 \times (|S_1| + |S_2| + \cdots)$

Oto optymalizacja, która może jeszcze bardziej poprawić wydajność. Zasadniczo możesz użyć iterowanego podwajania, aby znaleźć najmniejsze takie jak . W szczególności dla każdego elementu śledzimy najmniejszy podzbiór którego gcd wynosi i którego rozmiar wynosi . (Kiedy usuwasz duplikaty, rozwiązujesz powiązania na korzyść mniejszego podzbioru.) Teraz zamiast obliczać sekwencję dziewięciu zestawów $k$ $1 \in S_k$ $x \in S_i$ $S_1$ $x$ $\le i$ , zamiast tego obliczamy sekwencję pięciu zestawów , obliczając , następnie , a następnie , a następnie $S_1,S_2,S_3,S_4,\dots,S_9$ $S_1,S_2,S_4,S_8,S_9$ $S_2 = S_1 \otimes S_1$ $S_4 = S_2 \otimes S_2$ $S_8 = S_4 \otimes S_4$ $S_9 = S_1 \times S_8$ . Idąc, znajdź pierwszą taką, że . Po znalezieniu takiego, że , możesz natychmiast zatrzymać: możesz znaleźć najmniejszy podzbiór, którego gcd ma wartość , patrząc na podzbiór powiązany z . Możesz więc zatrzymać się, gdy tylko osiągniesz zestaw taki jak , co pozwala ci zatrzymać się wcześniej, jeśli znajdziesz mniejszy podzbiór. $k \in [1,2,4,8,9]$ $1 \in S_k$ $k$ $1 \in S_k$ $1$ $1$ $S_k$ $1 \in S_k$

Powinno to być wydajne czasowo i zajmować mało miejsca. Aby zaoszczędzić miejsce, dla każdego elementu nie musisz przechowywać całego zestawu: wystarczy przechowywać dwa wskaźniki wsteczne (więc dwa elementy , z których pobrałeś gcd, aby uzyskać ) i opcjonalnie rozmiar odpowiedniego podzbioru. $x \in S_k$ $S_i,S_j$ $x$

Zasadniczo można zastąpić sekwencję dowolnym innym łańcuchem dodawania . Nie wiem, czy jakiś inny łańcuch dodatków będzie lepszy. Optymalny wybór może zależeć od rozkładu poprawnych odpowiedzi i oczekiwanych rozmiarów zbiorów , co nie jest dla mnie jasne, ale prawdopodobnie można je uzyskać empirycznie poprzez eksperymenty. $[1,2,4,8,9]$ $S_k$

Kredyty: Moje podziękowania dla KWillets za pomysł przechowywania podzbioru liczb wraz z każdym elementem , który pozwala wcześnie się zatrzymać. $S_i$

— DW
źródło

Uważam, że wyszukiwanie binarne nie jest konieczne; możesz przechowywać liczbę elementów z każdym gcd i ustawić minimalną sumę par podczas każdego podwajania.

— KWillets

Świetny punkt, @KWillets! Dziękuję za ten piękny pomysł! Włączyłem to do mojej odpowiedzi.

— DW

0

Być może jest to szybsze spojrzenie na to w inny sposób ... największa liczba pierwsza mniejsza niż to 31607, dla całkowitej liczby 3401 liczb pierwszych między 2 a 31607, niezbyt duża liczba. Zapisz każdą z liczb, które otrzymałeś, w pełni ujęte w liczbach pierwszych do 31607: Tutajjest liczbą pierwszą lub dużą liczbą pierwszą. Następnie zestaw z„y jest względnie pierwsze, jeżeli odpowiedniewektory są liniowo niezależne (i ichy są różne lub obu 1), a szukająstopniamacierzy. $\sqrt{10^9}$

a_{i} = p_{1}^{n_{i 1}} p_{2}^{n_{i 2}} \dots P_{i}

$a_i = p_1^{n_{i 1}} p_2^{n_{i 2}} \ldots P_i$

P_{i}

$P_i$

a_{i}

$a_i$

n_{i j}

$n_{i j}$

P

$P$

— vonbrand
źródło

Jaki jest związek z niezależnością liniową? Wektory

i

są liniowo niezależne, ale GCD jest

a my chcemy

.

(1, 1)

$(1,1)$

(1, 0)

$(1,0)$

(1, 0)

$(1,0)$

(0, 0)

$(0,0)$

— Yuval Filmus

1

Wydaje się, że liniowa niezależność nie działa, ale możemy wykorzystać ten podstawowy rozkład w inny sposób. Dla każdej liczby pierwszej

(spośród

maksymalnie

) zdefiniuj zestaw

jako zbiór wszystkich liczb (spośród danego zestawu), które nie mają

jako czynnika. Problem polega teraz na znalezieniu najmniejszego podzbioru liczb

takiego jak dla każdego

,

. Jest to problem z zestawem uderzeń, równoważny z problemem z zestawem osłon. To jest

p

$p$

3401

$3401$

p_{i}

$p_i$

500

$500$

P_{i}

$P_i$

A_{p}

$A_p$

p

$p$

B

$B$

A_{p}

$A_p$

| A_{p} \cap B | \geq 1

$|A_p \cap B| \geq 1$

N P

$NP$ -kompletne, ale mogą istnieć pewne implementacje wystarczająco szybkie dla tego rozmiaru.

— polkjh

Czy możesz skierować mnie do niektórych implementacji, które mogłyby działać? Do tej pory mogę znaleźć tylko algorytmy aproksymacyjne. Dzięki!

— Wakaka

Ten artykuł ankietowy przedstawia zarówno przybliżone, jak i dokładne rozwiązania. Odpowiadając na komentarz, dodaj @ nazwisko osoby do komentarza. Wyśle powiadomienie do tej osoby. W przeciwnym razie mogą nawet nie wiedzieć o twoim komentarzu.

— polkjh 18.03.13

-1

Jeśli jesteś w stanie znaleźć podzbiór z gcd (S) = 1, wtedy zawsze mogę usunąć zbędne elementy z podzestawu, aż pozostaną tylko 2 elementy, które mają gcd (S) = 1. Dlatego mogę twierdzić, że albo najmniejszy podzbiór będzie zawierał 2 elementy lub nie będzie istniał.

Teraz używamy rekurencji, aby rozwiązać ten problem. Podzielmy tablicę liczb na 2 części, jedną z elementami n-1 i jedną z 1 elementem (ostatni element). Albo 2 liczby będą w pierwszych n-1 elementach, albo będzie jeden element z 1. części połączonej z ostatnim elementem. Dlatego jesteśmy w stanie rozwiązać ten problem

T (n) = T (n-1) + O (n) czas. co oznacza T (n) = O (n ^ 2).

— Pratik
źródło

4

gcd (6, 10, 15) = 1

$\gcd(6,10,15)=1$