結果
問題 |
No.16 累乗の加算
|
ユーザー |
|
提出日時 | 2016-08-04 14:50:51 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 94 ms / 5,000 ms |
コード長 | 770 bytes |
コンパイル時間 | 39 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-06-26 05:15:51 |
合計ジャッジ時間 | 2,032 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
コンパイルメッセージ
Syntax OK
ソースコード
class Calc0016 def initialize(args) args = args.map { |l| l.chomp.split(/\s+/) } @x, @n = args.shift.map(&:to_i) @as = args.shift.map(&:to_i) @m = 1_000_003 build_pow_table end def run r = 1 bs = @as.sort.reverse bs.each_cons(2).map { |a1, a2| a1 - a2 }.each do |s| r = r * pow(s) % @m + 1 end r = r * pow(bs.last) % @m r end def pow(k) r = 1 k.to_s(2).split(//).reverse.each_with_index do |b, i| r = (r * @pow_table[i]) % @m if b == '1' end r end def build_pow_table prev = @x @pow_table = [@x] (1..100_000_000.bit_length).each do |i| prev = (prev * prev) % @m @pow_table << prev end end end puts Calc0016.new(STDIN.readlines).run if __FILE__ == $0