AtCoder BC097 B: Exponential

問題

B - Exponential
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

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

ただし、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]

コメント

タイトルとURLをコピーしました