UAPC 2011 C Time Manipulation

問題

1,2,3,...,nの数がある。
このうちm個の整数p[i]に対して、いずれでも割りきれない数が、等しい確率で選ばれるとき、
選ばれる数字の期待値を求める。

方針

mが小さいので部分集合を全列挙して、包除原理で足したり引いたりすればいい。

ソースコード

int main(){
  ll n,m,p[30];
  while(cin>>n>>m,n){
    rep(i,m){
      cin>>p[i];
      if(p[i]<0)p[i]*=-1;
      if(p[i]==0)i--, m--;
    }
    sort(p,p+m); m=unique(p,p+m)-p;
    vi v;
    rep(i,m){
      bool ok=1;
      rep(j,m)if(i!=j&&p[i]%p[j]==0)ok=0;
      if(ok)v.pb(p[i]);
    }
    m=v.size();
    rep(i,m)p[i]=v[i];
    
    double sum=0; ll num=0;
    
    rep(i,1<<m){
      int sign=__builtin_popcount(i)%2?-1:1;
      
      ll prod=1,mx,gcd;
      rep(j,m)if(i&1<<j){
        gcd=__gcd(prod,p[j]);
        if(prod>1.0*n*gcd/p[j]+1e-12){
          goto NEXT;
        }
         prod*=p[j]/gcd;
      }
      mx=n/prod;
      num+=sign*mx; //cerr<<sign*mx<<endl;
      sum+=sign*prod*mx*(mx+1)/2;
      NEXT:;
    }
    //cerr<<sum<<" "<<num<<endl;
    printf("%.20f\n",num?sum/num:0);
  }
  return 0;
}