結果

問題 No.28 末尾最適化
ユーザー letrangerjpletrangerjp
提出日時 2017-06-13 15:37:13
言語 Ruby
(3.4.1)
結果
AC  
実行時間 2,693 ms / 5,000 ms
コード長 503 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 66,560 KB
最終ジャッジ日時 2024-09-24 16:57:38
合計ジャッジ時間 3,381 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 99 ms
12,288 KB
testcase_01 AC 2,693 ms
66,560 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