日記

TopCoder Marathon Match 58 IsolatedPrimes

与えられた a, b, x で、 素数p に対して、(p - a) から (p + b) の範囲で x 個の素数がある(x個にpを含む)、 という最小の p を求めよ。

ぱっと見、すげー簡単な問題に見えるんだけど、問題は最大 2^64 ってところだな。

2^32 なら余裕で数え上げられるんだけど、さすがに 2^64 だとなぁ。

x が500までってのがせめてもの救いですか? たぶん 2^64 まで見る必要は全然ないんだろうね。

a, b で範囲が変動するので、密度が変わっちゃうってのもあるな。

思いつくことは色々あるけど、コンテスト中は発言不可だから、このへんで。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-03-25 (木) 10:39:47 (2798d)