AOJ 2446 - Enumeration

スーパー包除原理マン

問題

n個の整数aとn個の整数pと整数mが与えられる
i番目の整数a[i]をp[i]%の確率で選ぶ、という操作を各iについて行い、0個以上n個以下の整数を選ぶ
1以上m以下の整数の中で、選ばれた整数の少なくとも1つで割り切れるものの個数の期待値を求めよ

1 <= n <= 20
1 <= m <= 10^18
1 <= a[i] <= 10^18
1 <= p[i] <= 99

解法

n個の整数aのある部分集合Sについて、
f(S): 1以上m以下の整数のうち、Sの全ての要素で割り切れるようなものの個数の期待値
とすると、包除原理より答えは
Σ f(S) * (-1)^(|S|+1)
となる (ここまでテンプレ)

Sの全ての要素で割り切れる数ってのは、Sの各要素のLCMで割り切れる数ってこと
Sを2^n通り全部試して、包除原理の符号に気を付けつつ
個数) 各要素のLCMでmを割った値
と
確率) 各要素を選ぶ確率の積
の積(=f(S))を足し合わせていけばいい

実装

LCMを求めるメソッドをちょっと改良して、オーバーフローする場合は2^60を返すようにした
今回はm <= 10^18 < 2^60だからこうすればオーバーフローしたときは答えが変動しないようになる

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {
	ll g = gcd(a,b);
	ll res = a/g*b;
	if (res/b != a/g) return 1ll<<60;
	return res;
}

ll n, m, a[22], x[22];
double res;

signed main() {
	cin >> n >> m;
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> x[i];
	reps(b,1,1<<n) {
		double p = 1;
		ll lc = 1;
		rep(i,n) if (b>>i&1) {
			p *= 1.*x[i]/100;
			lc = lcm(lc,a[i]);
		}
		p *= m/lc;
		if (__builtin_parity(b)) res += p;
		else res -= p;
	}
	printf("%.14lf\n",res);
}