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); } }