問題
考察
$$a < b < c$$
$$a, b, c:素数$$
$$a^2×b×c^2≦N$$
これらを満たす$a,b,c$の組み合わせはいくつありますかという問題です。便宜上、上から条件①・②・③とします。制約が$N≦10^{12}$と緩いこともあり、どこから手をつければいいか分かりづらいかもしれません。ですが、$a,b,c$について、「大きくてもどれくらいの大きさにしかならないか。」上界を見積もることで活路が見えてくるかと思います。
cの上界
cについて大きくてもどれくらいの大きさに留まりそうかを考えてみます。条件①・②には当てはまりませんが、仮に$a = b = 1$の場合、条件③は$c^2≦N$となります。すると、$c$は大きくても$10^6$までに留まるが分かります。
aの上界
aについても考えてみます。条件①に当てはまりませんが、仮に$a = b = c$の場合、条件③は$a^5≦N$となります。正確には計算してませんが、$a$は大きくても$10^3$にもならないことが分かります。
計算量的に間に合いそうな方針を考える
今までの内容から、$a$は大きくても$10^3$、$c$は大きくても$10^6$までには留まります。もし、$a$と$c$に対して全探索をした場合、計算量は$10^9$程度になります。これでは計算量的に間に合いそうにありません。しかし、$a$と$c$は条件②から素数です。素数であることを考慮すると$a$になり得るのは多くても約170個、$c$は約78000個です。もし、$10^6$ぐらいまでの素数のリストを事前に用意できれば、$a$と$c$に対して全探索をしても間に合いそうです。
$a$と$c$に対して全探索が間に合うのであれば、「$a$と$c$を固定した時、$b$としてあり得る値は何個あるか？」をそれぞれ求め、合計するという方針がとれます。この方針で考えていきましょう。
ここまでを整理します
- $a$は大きくても$10^3$までの素数
- $c$は大きくても$10^6$までの素数
- 下記のことができれば、$a$と$c$に対して全探索して答えを求めることができる
- 事前に素数のリストを用意する
- 「$a$と$c$を固定した時、$b$としてあり得る値は何個あるか？」を求める
事前に素数のリストを用意する
事前に素数のリストを用意しておく必要があります。素数のリストの求め方については調べると様々な記事が見つかります。それらを参考にして用意していきましょう。
以下の記事が実際に参考になります。
「aとcを固定した時、bとしてあり得る値は何個あるか？」
$a$と$c$は固定できています。そうすると、条件③から、$b≦\dfrac{N}{a^2×c^2}$を満たします。これを満たす$b$が何個あるかについては素数のリストがあれば二分探索で求めることができます。あとは、条件①もあることにも注意しておきます。具体的には下記の2点も考慮しておきましょう。
- $a$以下の素数は$b$としてあり得る値に含めないようにする
- $c$以上の素数は$b$としてあり得る値に含めないようにする
これで、「aとcを固定した時、bとしてあり得る値は何個あるか？」を求めることができます。
長くなりましたが、これで$a$と$c$を全探索、そしてあり得た$b$の個数をそれぞれを合計することで答えを求めることができます。
計算量的にも十分間に合います。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。
参考