結果

問題 No.28 末尾最適化
ユーザー letrangerjpletrangerjp
提出日時 2017-06-13 15:37:13
言語 Ruby
(3.2.2)
結果
AC  
実行時間 2,666 ms / 5,000 ms
コード長 503 bytes
コンパイル時間 113 ms
コンパイル使用メモリ 11,896 KB
実行使用メモリ 75,200 KB
最終ジャッジ日時 2023-10-24 21:47:39
合計ジャッジ時間 3,383 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 99 ms
16,224 KB
testcase_01 AC 2,666 ms
75,200 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #

require "prime"

Q = gets.to_i
Queries = Q.times.map{
  gets.split.take(4).map(&:to_i)
}

class Integer
  def f
    return to_enum(:f) unless block_given?
    x = self
    loop{
      yield x
      x = 1 + (x * x + x * 12345) % (10**8+9)
    }
  end
end

Queries.each{|seed, n, k, b|
  factors = b.prime_division
  a = seed.f.take(n+1)
  p factors.map{|f,g|
    z=a.map{|v|
      cnt = 0
      while v % f == 0
        cnt += 1
        v /= f
      end
      cnt
    }.sort[0...k]
    z.sum/g
  }.min
}
0