巨大な整数のN乗根を求める。 某CTFで使った

n-root.rb

#!/usr/bin/env ruby
# vim:fileencoding=utf-8

# xのn乗根
def root(x, n)
    r = 0
    a = 1 << (Math.log(x) / n / Math.log(2))
    while a > 0
        ra = r | a
        d = x - ra ** n
        return ra if d == 0
        r    = ra if d  > 0
        a >>= 1
    end
    return nil
end

# xはパイプで、nは引数で指定する
# 例: echo 1727094849536 | ruby n-root.rb 7
x = STDIN.read.to_i
n = ARGV[0].to_i

puts root(x, n) || '整数の答えはない'