AtCoder Beginner Contest 193 C – Unexpressed を解いた記録
問題の概要
正の整数\(N\)が与えられる．\(1\)以上\(N\)以下の整数のうち，\(2\)以上の整数\(a, b\)を用いて\(a^{b}\)と表せないものの個数を数えよ．
制約
- \(1 \leq N \leq 10^{10}\)
- 入力はすべて整数
解法
\(1 \leq N \leq 10^{10}\)となっていることから，\(N\)以下の正の整数すべてに対して\(a^{b}\)の形で表現できるかを調べるわけにはいきません．
\(a^{b}\)の形で表現できる数がいくつかあるかを数えることにしましょう．\((10^{5})^{2}=10^{10}\)より，\(2 \leq a \leq 10^{5}\)としてよいことがわかります．
また，\(2^{34} \sim 1.7 \times 10^{10}\)より，\(2 \leq b \leq 33\)となることもわかります．これなら\(a, b\)を全探索しても間に合います．
しかし，例えば\(4^{b}\)という形の整数はすべて\(2^{b}\)という形でも表現できます．
\(a^{b}\)の形で表現できる数を重複なく全列挙するためには，まず\(a\)の候補から\(a^{b}\)の形で表せる数を除外する必要があります．
\(2 \leq a \leq 10^{5}\)よりエラトステネスのふるいを使いたくなるところですが（実際，私がコンテスト中に使った解法はエラトステネスのふるいを一部改変したものです），
素数のみを\(a\)の候補とするのでは不十分です．これだと，例えば\(6^{b}\)の形で表せる数を見落としてしまいます．
私がコンテスト中に用いた解法は，
- エラトステネスのふるいを一部改変し，\(a^{b}\)の形で表せない数\(a (2 \leq a \leq 10^{5})\)を列挙する．
- それぞれの\(a\)について\(b\)の最大値を求め，\(a^{b}\)の形で表せる数の個数を調べる．
というものです．通常のエラトステネスのふるいでは，素数を見つけたときにその素数の倍数を素数候補から削除します．
今回はこの部分を改変し，「\(a^{b}\)の形で表せない数」を見つけたとき，その数を\(a\)として\(a^{b}\)の形で表せる数を\(a\)の候補から削除します．
実装例
感想
C問題とは関係ありませんが，2021年2月のABC(ABC191, ABC192, ABC193)ではD問題を解けずに終わることが2回ありました．
しばらくABC5完から遠ざかっているので，3月中に1回くらいはABCで5完したいものです．