큰 무작위로 선택된 정수가 일부 세트의 정수에 의해 나눌 수없는 확률을 결정하기위한 효율적인 알고리즘이 있습니까?

Question

10 개의 정수 $ a= a_1, a_2, \ cdots a_ {10} $ 의 확률이 무엇인지 알 수있는 효율적인 알고리즘이 있습니다. $ 1 $ 및 $ 10 ^ {10} $ 사이의 무작위로 선택된 정수는 이 아닙니다 이 세트의 모든 구성원이 나눌 수 있습니다.

나는이 문제를 해결하기 위해 포함 제외 원칙을 사용할 수 있지만 효율적으로 작동하도록 구현하는 방법을 알아낼 수는 없습니다.

note : "효율적"이라고 말할 때, 나는 다항식 시간을 의미하지만, 다항식 시간이 다항식이 고정되어 있기 때문에 다항식 시간이 아닌 것으로 인정되는 것은 전적으로 확신하지 못합니다.

Answer 1

$ \ mathbf x $ 범위 $ 1, \ ldots, n $ 및 $ e_i $ $ \ mathbf x $ 이 $ A_I $ . $ e_1, \ ldots, e_m $ 일어나는 이벤트가없는 확률에 관심이 있습니다 (귀하의 경우 $ m= 10 $ ). 포함 제외 원칙을 사용하여 $ e_ {i_1} \ LARD \ CDOTS \ LAND E_ {I_K} $ 의 이벤트 확률을 계산하는 것으로 감소합니다. 즉, $ \ mathbf x $ 은 $ a_ {i_1}, \ ldots, a_ {i_k}에 의해 나눌 수 있습니다. $ . $ \ mathbf x $ 은 LCM이 나눌 수없는 경우 숫자의 숫자로 나눌 수 있으므로 $ \ mathbf x $ 은 $ a $ 에 의해 나눌 수 있습니다.

$ 1, \ ldots, n $ 중 $ a $ 에 의해 나눌 수있는 숫자는 $$ a, 2a, 3a, \ ldots, \ lfloor n / a \ rfloor a, $$ 총 $ \ lfloor N / A \ RFLOROR $ 숫자. 따라서 $ \ mathbf x $ 확률은 $ a $ 이 정확히 나타납니다. $$ \ frac {\ lfloor n / a \ rfloor} {n}. $$