C'è un algoritmo efficiente per determinare la probabilità, un numero intero scelto a caso non è divisibile da qualsiasi numero intero di alcuni set?

Question

Dato un set di 10 numeri interi $ a= a_1, a_2, \ cdots A_ {10} $ , c'è un algoritmo efficiente che può dirmi qual è la probabilitàUn numero intero scelto a caso tra $ 1 $ e $ 10 ^ {10} $ è non > Divisibile da qualsiasi membro di questo set.

Comprendo il principio di inclusione-esclusione può essere utilizzato per risolvere questo problema, ma non riesco a capire come implementarlo in modo che funzioni in modo efficiente.

Nota : Quando dico "efficiente", intendo il tempo polinomiale, ma non sono del tutto sicuro che cosa si qualifica come momento polinomiale è questo caso in cui entrambe le variabili sono fisse.

Answer 1

Let $ \ MathBF x $ essere un numero casuale nell'intervallo $ 1, \ Ldots, n $ , e lascia che $ E_i $ denota l'evento che $ \ mathbf x $ è divisibile con $ a_i $ . Sei interessato alla probabilità che nessuno degli eventi $ E_1, \ LDOTS, E_M $ accada (nel tuo caso, $ m= 10 $ ). Utilizzando il principio di inclusione-esclusione, ciò riduce il calcolo della probabilità degli eventi del modulo $ e_ {i_1} \ Land \ cdots \ Land E_ {i_k} $ , cioè, $ \ mathbf x $ è divisibile da parte di $ a_ {i_1}, \ ldots, a_ {i_k} $ . Dal momento che una classe $ \ Mathbf x $ è divisibile da un gruppo di numeri IFF è divisibile dal loro LCM, è sufficiente determinare la probabilità che $ \ mathbf x $ è divisibile da $ a $ .

tra $ 1, \ Ldots, n $ , i numeri divisibili di $ A $ sono $$ a, 2a, 3a, \ ldots, \ lfloor n / a \ rfloor a, $$ In totale $ \ lfloor n / a \ rfloor $ numeri. Da qui la probabilità che $ \ mathbf x $ è divisibile di $ A $ è esattamente esattamente $$ \ frac {\ lfloor n / a \ rfloor} {n}. $$