2015年2月8日日曜日

yukicoder 144 エラトステネスのざる

問題

http://yukicoder.me/problems/242

解法

2~Nの間の各数字iに対してPr{iが生き残る}を計算する.
E{残った数字の個数} = Σ( E{1{iが生き残る}}) = ΣPr{iが生き残る}
となるので計算したものの総和でおk.
Pr{iが生き残る}はエラトステネスで倍数のやつに1-p倍するみたいなことをする.

こういう問題をぱっと解けるようになりたい



0 件のコメント:

コメントを投稿