AOJ 2446 Enumeration

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446&lang=jp

解法

簡単のために，試しに2つの数字 a, b を用意して考えてみます．a, b が選ばれる確率をそれぞれ p, q とします．
まず，a のみを選んだ場合の期待値は，

• (m / a) * p * (1 - q)

となります．
b のみを選んだ場合は，

• (m / b) * (1 - p) * q

となります．
最後に a と b の両方を選んだ場合は，

• (m / a + m / b - m / lcm(a, b)) * p * q

となります．
これらを足し合わせてみると，以下のようなきれいな式になります．

• (m / a) * p + (m / b) * q - (m / lcm(a, b)) * p * q

これは一般の場合でも成り立つので，結局包除原理で簡単に求めることが出来ます． 2^n 通り試してやればよいです．
lcm のオーバーフローに注意．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

constexpr ll INF = 2e18;
constexpr ll invalid = -1;

ll lcm(ll a, ll b) {
    ll g = __gcd(a, b);
    a /= g;
    if(a > INF / b) {
        return invalid;
    }
    return a * b;
}

int main() {
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n);
    vector<double> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i] /= 100;
    }

    double res = 0;
    for(int S = 1; S < 1 << n; ++S) {
        int cnt = 0;
        double q = 1;
        for(int i = 0; i < n; ++i) {
            if((S >> i) & 1) {
                cnt++;
                q *= p[i];
            }
        }

        ll t = 1;
        for(int i = 0; i < n; ++i) {
            if((S >> i) & 1) {
                t = lcm(t, a[i]);
            }
            if(t == invalid) {
                break;
            }
        }
        if(t != invalid) {
            if(cnt & 1) {
                res += q * (m / t);
            } else {
                res -= q * (m / t);
            }
        }
    }

    cout << fixed << setprecision(10) << res << endl;
}