【Python】ABC - 097 - Exponential

　問題

与えられた数字$X$以下で最大となるべき乗数を求める問題。べき乗数は1以上の整数$b$と2以上の整数$p$を使って$b^p$とかける整数のことを指す。

方針

基本的には、$X$以下の範囲の中で、$bとp$を全探索する方針は立ったが、あまり深く考えずに$bとp$をそれぞれ$X$まで探索したところTLEに。。。
ちゃんと証明する必要があると思うが、$\sqrt　X$付近までの探索で十分だろうと判断して18msでAC。

import math
X = int(input())
res = 0
for b in range(1, int(math.sqrt(X))+1): # sqrt(X)付近まで探索
    for p in range(2, int(math.sqrt(X))+2): # sqrt(X)付近まで探索
        val = b**p
        if (val <= X) and (val > res): # X以下かつその値が最大値なら値を更新
            res = val
print(res)

追記

@konandoiruasa にコメントいただきましたので、$b,p$の範囲に関して追記する。

$bはp$が2のときが最大になるので、$1 \leq b \leq \sqrt X$となる。

$p$は$X \geq b^p$を満たせば良いので、

X \geq b^p \\
\log X \geq p \log b \\
\therefore p \leq \frac{\log X}{\log b}

となる。