スポンサーサイト

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

SRM 524 Div2 medium

easy に引き続き medium 問題の解説

medium 問題

あなたは n (1以上10^12以下)個のマジックダイヤモンドを見つけました.
これらのダイヤを魔法で運びます.
x 魔法 (x は整数) を使うと x 個のダイヤを運ぶことができます.
しかし,x が素数の場合は,ダイヤを運べずに失ってしまいます.
また残っているダイヤの個数以上の魔法は使えません.
失わないように運ぶためには複数回魔法を使わなければならない場合もあります.
これらのダイヤを運ぶために,魔法を使う回数の最小値はいくらになるか求めなさい.


例:

8個のダイヤモンドがある場合.
8は素数ではないので 8 魔法を使ってよい.
よって1回で全てを運べる.


13個のダイヤモンドがある場合.
13は素数でなので 13 魔法は使えない.
なので素数ではない 9 と 4 に分けて運ぶ.(他の組み合わせもあり)
よって2回で全てを運べる.


続きから解説.

問題文には魔法だの何だのと書いたけど,要するに与えられた数をいくつの素数以外の数の和で表すことができるかという問題.

まず素数であるかどうかチェック.

素数でないならそのまま 1 回で運ぶことができる.

素数なら分解しなければいけないのだけれど,実は 3 より大きい素数は全て 2 回で運ぶことができる.

素数は 2 で割ることができない.ということは (素数 - 1) は 2 で割れるので素数ではない.

よって素数だった場合は (素数 - 1) 魔法と 1 魔法を使えばよいことになる.

3の場合だけ 1 引いた数の 2 も素数なので,1 魔法を1回使わなければならない.


私は3の場合忘れてて落とされたんですけどね(ぇ
スポンサーサイト

コメントの投稿

非公開コメント

お知らせ
相互リンクしてくださる方募集してます!!
Twitter 相互フォロワ―も募集してます!!
コメントも募集してます!!
感想でも質問でも気軽にどうぞ!!

ランキング参加してます!!
クリックお願いします!!

にほんブログ村 高校生日記ブログ 高専生へ
検索フォーム
最新コメント
リンク
admin
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。