Существует ли эффективный алгоритм для определения вероятности большого случайно выбранного целого числа, не делится любого целого числа некоторых наборов?

Question

Учитывая набор из 10 целых чисел $ a= a_1, a_2, \ cdot a_ {10} $ , есть ли эффективный алгоритм, который может сказать мне, какова вероятностьСлучайно выбранное целое число между $ 1 $ и $ 10 ^ {10} $ не Добрима с любым членом этого набора.

Я понимаю, что принцип исключения включения может быть использован для решения этой проблемы, но я не могу выяснить, как это реализовать его так, чтобы он был эффективно работает.

Примечание : Когда я говорю "Эффективно", я имею в виду многочленное время, но я не совсем уверен, что квалифицируется как полиномиальное время, так как оба переменные фиксируются.

Answer 1

Пусть $ \ mathbf x $ Будьте случайным числом в диапазоне $ 1, \ ldots, n $ И позвольте $ E_I $ Обозначим событие, которое $ \ mathbf x $ делится на $ a_i $ . Вы заинтересованы в вероятности того, что ни одно из событий $ e_1, \ ldots, e_m $ происходит (в вашем случае $ m= 10 $ ). Используя принцип исключения включения, это уменьшает для вычисления вероятности событий формы $ E_ {I_1} \ Land \ CDOTS \ LANG E_ {I_K} $ , То есть $ \ mathbf x $ делится всеми $ a_ {i_1}, \ ldots, a_ {i_k} $ . Поскольку $ \ mathbf x $ делится с помощью куча чисел IFF, это делится по их LCM, достаточно определить вероятность того, что $ \ mathbf x $ делится на $ a $ .

среди 1 $, \ ldots, n $ , числа, делимые на $ a $ $$ A, 2A, 3A, \ Ldots, \ lfloor n / a \ Rfloor a, $$ Всего $ \ lfloor n / a \ Rfloor $ номера. Следовательно, вероятность того, что $ \ mathbf x $ делится на $ a $ точно $$ \ frac {\ lfloor n / a \ Rfloor} {n}. $$