問題概要
3つの整数が与えられます。
かつ
となるような
のうち、
が最大となるようなペアを求めてください。
制約は、です。
解法
まずはエラトステネスの篩を利用して、素数を洗い出します。
について全探索をすると、
の最適解は、ある
に対して、
、
を満たすような最大の素数になります。
ので、二分探索での最大値を毎回求め、答えを求めていけばよいです。
のですが、AC後に他の解説ブログを見たところ、という制約のおかげで、
も全探索できるらしいです…ちょうど調和級数の形になりますね。
感想
篩で洗い出す素数の個数を2回間違えました(最初は少なすぎてWAが出て、その後増やしすぎてTLEになりました)…反省します。
