AOJ : 1076 - Time Manipulation

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076
問題文が日本語なので, そちらをご覧ください.

アルゴリズム

包除原理で解くことができます.
N以下のp[1]の倍数の個数, N以下のp[2]の倍数の個数,..., N以下のp[M]の倍数の個数, をそれぞれひとつの集合として, ベン図を書いてみればわかると思います.
この問題では, 上記の集合の外側の集合を求めるだけです.

プログラム

このプログラムでは, 問題文のNとMと逆になっているので注意です.

//1+2+...+nを求める
ll sum(ll n){
  return n * (n + 1) / 2;
}

//aとbの最小公倍数を求める
ll lcm(ll a,ll b){
  return a / __gcd(a,b) * b;
}

int main(void){
  ll m,n;
  ll t[22];

  while(cin>>m>>n,m||n){
    rep(i,n){
      cin>>t[i];
    }

    ll to = (1<<n);
    ll p = sum(m), q = m; //期待値の分子と分母

    //ベン図でのどの集合かを2進数(i)で決める
    //例えば, サンプル1で, 110 ならば, 6の倍数の集合(2と3のlcm)  
    for(ll i=1;i<to;i++){
      ll bitCnt = 0; //ビットがいくつ立っているか求める
      ll l = 1; //最小公倍数がいくらか

      for(ll bit=1,j=0;bit<=i;bit<<=1,j++){
        if(i & bit){
          bitCnt++;
          l = lcm(l,t[j]);
        }
      }

      //ベン図で奇数個の集合が重なっている場合, マイナス
      if(bitCnt % 2 == 1){
        p -= l * sum(m / l); //l * sum(m / l) : m以下のlの倍数の合計
        q -= m / l;          //m / l : m以下のlの倍数の数
      }
      //ベン図で偶数個の集合が重なっている場合, プラス
      else{
        p += l * sum(m / l);
        q += m / l;
      }
    }

    printf("%.10f\n",q==0 ? 0 : (double)p/q);
  }
}