Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

[C79] 承認待ちコメント

このコメントは管理者の承認待ちです

[C80] 承認待ちコメント

このコメントは管理者の承認待ちです

[C81] 承認待ちコメント

このコメントは管理者の承認待ちです

[C82] 承認待ちコメント

このコメントは管理者の承認待ちです

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2472-9f4e1943
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 16282 - Horace and his primes [TAP2013H] (この記事を編集する[管理者用])

Source

SPOJ 16282 [TAP2013H]
Argentinian Programming Tournament 2013

問題概要

正整数 $n$ に対して,$f(n)$ を $n$ を割り切る素数の和で定義する.
$n$ を $f(n)$ に置き換えていく手順を繰り返すといずれ $n$ は素数になる.
$n$ から始めた時,素数になるまでに必要な手順の数 $+1$ を $g(n)$ とする.
$P$ 個のテストケースが与えられる.
各テストケースでは $A \leq n \leq B$ かつ $g(n) = K$ を満たす $n$ の個数を求める.
$1 \leq P \leq 10^5$
$2 \leq A \leq B \leq 10^6$
$1 \leq K \leq 10^6$

解法

$g(n)$ の最大値は $12$ 程度なので,$1\leq K \leq 12$ に対して,$g(n)=K$ となる $x$ 以下の $n$ の数を前計算しておく.
$f(n)$ の値は篩っぽく求めて,$n > f(n)$ なので,$g(n)$ の値はDPで計算できる.

コメント

[C79] 承認待ちコメント

このコメントは管理者の承認待ちです

[C80] 承認待ちコメント

このコメントは管理者の承認待ちです

[C81] 承認待ちコメント

このコメントは管理者の承認待ちです

[C82] 承認待ちコメント

このコメントは管理者の承認待ちです

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2472-9f4e1943
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。