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)$。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *