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$

Znalezienie rozmiaru najmniejszego podzbioru z GCD = 1

Odpowiedzi: