問題一覧 > 通常問題

No.237 作図可能性

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 203
作問者 : evimaevima
3 ProblemId : 239 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:23

問題文

整数 $A$ が与えられます。 $3$ 以上 $A$ 以下の整数 $n$ のうち、定規とコンパスによって正 $n$ 角形が作図可能であるようなものの個数を求めてください。

定規とコンパスによる作図、およびこの問題を解く上で必要な知識に関しては Wikipedia を参照してください: http://ja.wikipedia.org/wiki/定規とコンパスによる作図

入力

$A$

  • $3 \le A \le 10^9$

出力

条件を満たす整数 $n$ の個数を出力し、末尾で改行せよ。

サンプル

サンプル1
入力
9
出力
5

正三角形、正四角形、正五角形、正六角形、正八角形はいずれも定規とコンパスにより作図可能ですが、正七角形と正九角形は作図不可能です。

サンプル2
入力
1000000000
出力
456

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。