Trouver la taille du plus petit sous-ensemble avec GCD = 1

Il s'agit d'un problème de la session de pratique du Polish Collegiate Programming Contest 2012 . Bien que je puisse trouver les solutions pour le concours principal, je n'arrive pas à trouver la solution à ce problème n'importe où.

Le problème est le suivant: étant donné un ensemble de entiers positifs distincts ne dépassant pas 10 9 , trouvez la taille m du plus petit sous-ensemble qui n'a pas de diviseur commun autre que 1. N est au plus 500, et une solution peut être supposée exister.$N$$10^9$$m$$N$

J'ai réussi à montrer que . Mon raisonnement est le suivant: supposons qu'il existe un sous-ensemble minimal de taille S | S | = 10 , avec gcd = 1. Alors tous les 9 sous-ensembles de S doivent avoir gcd> 1. Il y a exactement 10 de ces sous-ensembles, et leurs gcd doivent être coprime par paire. Que ces pgcd soient 1 < g 1 < g 2 < . . . < g 10 , où gcd ( g i , g j ) = 1 , pour i $m \le 9$$S$$|S|=10$$S$$1 < g_1 < g_2 < ... < g_{10}$$\gcd(g_i,g_j)=1$ . Alors le nombre maximum dans S est g 2 g 3 . . . g 10 . Mais g 2 g 3 . . . g 10 ≥ 3 × 5 × 7 × 11 × . . . × 29 = 3234846615 > 10 9 , une contradiction.$i \neq j$$S$$g_2g_3...g_{10}$$g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$

Cependant, même avec cela, une force brute simple est encore trop lente. Quelqu'un a-t-il d'autres idées?

Ce problème est équivalent au suivant, et il est trivial de construire une réduction dans les deux sens.

Étant donné une liste de vecteurs de bits, trouvez le nombre minimum d'entre eux de telle sorte que andtous résultent du vecteur de bit. ( ∗ $0$$(*)$

Ensuite, nous montrons que la couverture d'ensemble est réduite à . Par ensemble de couvertures, je veux dire étant donné une liste d'ensembles S 1 , … , S k , trouver le nombre minimum d'ensembles qui couvre leur union.$(*)$$S_1,\ldots,S_k$

Nous ordonnons que les éléments des ensembles soient . Soit f ( S ) = ( 1 - χ a 1 ( S ) , … , 1 - χ a n ( S ) ) , où χ x ( S ) = 1 si x ∈ S , 0 sinon. Notez que cette fonction est une bijection donc elle a un inverse.$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$

Maintenant, si nous résolvons sur f ( S 1 ) , … , f ( S k ) , et que les solutions sont { f ( S b 1 ) , … , f ( S b m ) } , alors { f - 1 ( S b 1 ) , … , f - 1 ( S b m ) $(*)$$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})\}$ est la solution pour définir la couverture.

Ainsi, je pense que ce problème teste sa capacité à tailler l'espace de recherche.

Il est possible de résoudre ce problème de manière relativement efficace en calculant tous les gcd par paire, en supprimant les doublons, puis en répétant. C'est le fait de supprimer les doublons avant de récurer qui le rend efficace.

$\otimes$$S,T$

$|S \otimes T| \le |S| \times |T|$$|S \otimes T| \le 10^9$$S \otimes T$$S \otimes T$$|S| \times |T|$

$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$. Si vous souhaitez également générer un exemple concret d'un tel sous-ensemble, en conservant des pointeurs en arrière, vous pouvez facilement reconstruire un tel ensemble.

$10^9$$500 \times (|S_1| + |S_2| + \cdots)$

$k$$1 \in S_k$$x \in S_i$$S_1$$x$$\le i$$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$$k \in [1,2,4,8,9]$$1 \in S_k$$k$$1 \in S_k$$1$$1$$S_k$$1 \in S_k$

$x \in S_k$$S_i,S_j$$x$

$[1,2,4,8,9]$$S_k$

$S_i$

$\sqrt{10^9}$

Si vous pouvez trouver un sous-ensemble avec gcd (S) = 1, alors je peux toujours supprimer les éléments redondants du sous-ensemble jusqu'à ce qu'il ne reste que 2 éléments, qui ont gcd (S) = 1. Par conséquent, je peux affirmer que soit le plus petit le sous-ensemble contiendra 2 éléments ou il n'existera pas.

Maintenant, nous utilisons la récursivité pour résoudre ce problème. Divisons le tableau de nombres en 2 parties, une avec n-1 éléments et une avec 1 élément (dernier élément). Soit les 2 nombres seront dans les n-1 premiers éléments, soit un élément sera présent à partir de la 1ère partie appariée avec le dernier élément. Par conséquent, nous sommes en mesure de résoudre ce problème en

T (n) = temps T (n-1) + O (n). ce qui signifie T (n) = O (n ^ 2).