Problem A

Problem A Space Coconut Crab (II)
Takahiro Koh
Yusuke Izumi
問題概要

下記の条件を満たす三角形は何種類ある
か？


三辺が全て素数である。
三辺の和が T となる。
送信状況



最初の正解：10 分 by echizen
総送信数：79
正解チーム数：27/28
解法

素数テーブルを求める。


エラトステネスの篩
foreach p in T/3 以下の全ての素数

foreach q in （T – p)/ 2 以下の全ての素数

r ( = T – p – q) は素数か？


エラトステネスの篩で素数テーブルを生成したときのフラ
グを流用。
p と q と r は三角不等式を満たすか？
散見された間違い

毎回素数判定をする。



整数 n が素数判定は（普通） O(√n)
エラトステネスの篩でテーブルを生成しておく
こと。
三角不等式忘れをきっと送信前にやった
はず。
最後に

この問題は簡単なので素早く確実に解くことがで
きるようにしましょう。



問題文を読むのが面倒だからといって安易に他の問
題に走らないように。
箇条書き部分、問題文の最終段落、入出力を先に読
むと題意をつかみやすい。
本問題はフィクションであり、実在の人物、団体と
は一切関係がないことになっております。

Download Report