FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SRM 400 DIV1 250 StrongPrimePower

ある数値nが与えられるので、n = p^q かつ p が素数となる p,q を求めよ、という問題。q > 1という条件と、2 <= n <= 10^18 という条件がある。
nの最大値が10^18だったので、エラトステネスのO(N^0.5)でもメモリも時間も足らんから数論かと思ってすぐ諦めた。が、答えをみると全然数論じゃなかった。情けない。
解法は大別して下の2種類。

■解法その1
p^2 となるパターンを先に検証すればあとは p^q (q>=3) だけになる。
そうするとpが検証可能な値になるので普通に判定するだけ。



■解法その2
pow。検証(s!=n)のときforでまわしてsを求めてるのはpow(p,q)にしたら最後のテストケースが通らなかったため。解法その1のL65をみるに、両方long doubleにしてしまえば問題ないっぽい。本番じゃ精度が怖くて書きたくないかも。

スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。