Jackpot

题意概述

给定$n$个数$P_i$，求$\lim_{k \to \infty} {S_k \over 2k+1}$，其中$S_k$表示区间$[-k, k]$中能被至少一个$P_i$整除的数的个数。

数据范围：$1 \le n \le 16, \ 1 \le P_i \le 10^9$。

算法分析

观察这个公式，可以发现这就是在所有整数中等概率选取一个数$X$，$X$能被至少一个$P_i$整除的概率。考虑一个非零整数$P$，$X$能被$P$整除的概率为${1 \over P}$。考虑多个整数$P_1, P_2, …, P_m$，$X$能被所有$P_i$整除的概率为${1 \over LCM(P_1, P_2, …, P_m)}$。

根据容斥原理，答案就是将某一个$P_i$整除$X$的概率加起来，再减去某两个$P_i$同时整除$X$的概率，再加上某三个$P_i$同时整除$X$的概率…由于$n \le 16$，直接枚举$P$的所有组合然后按上述方法进行计算即可。

理论上程序的时间复杂度是$O(2^n)$。