AtCoder BC097 B: Exponential

問題

https://abc097.contest.atcoder.jp/tasks/abc097_b

解法

b^pがX以下になる組み合わせについて考えます。

これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N²)で求めることが出来ます。

ただし、pについては計算結果がXを超えた時点で以降は打ち切ることが出来ます。

このようにして求めた冪乗のリストの内、X以下で最大のものを求めることで解けます。

実装

a = []
for i in 1..1000
    for j in 2..1000
        m = i ** j
        break if m > 1000
        a << m
    end
end
x = gets.chomp.to_i

b = a.sort.uniq.select{|v| v <= x}
puts b[-1]