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