結果

問題 No.811 約数の個数の最大化
ユーザー letrangerjp
提出日時 2019-04-12 21:56:26
言語 Ruby
(2.6.4p104)
結果
AC  
実行時間 794 ms
コード長 379 Byte
コンパイル時間 21 ms
使用メモリ 8,612 KB
最終ジャッジ日時 2019-09-20 22:32:15

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample_1 AC 15 ms
8,584 KB
sample_2 AC 19 ms
8,608 KB
sample_3 AC 692 ms
8,612 KB
testcase_1 AC 15 ms
8,584 KB
testcase_2 AC 17 ms
8,588 KB
testcase_3 AC 24 ms
8,608 KB
testcase_4 AC 54 ms
8,604 KB
testcase_5 AC 80 ms
8,608 KB
testcase_6 AC 315 ms
8,612 KB
testcase_7 AC 341 ms
8,608 KB
testcase_8 AC 216 ms
8,600 KB
testcase_9 AC 686 ms
8,608 KB
testcase_10 AC 169 ms
8,604 KB
testcase_11 AC 794 ms
8,608 KB
testcase_12 AC 780 ms
8,604 KB
テストケース一括ダウンロード
コンパイルメッセージ
Syntax OK

ソースコード

diff #
#!ruby -rprime
N, K = gets.split.map &:to_i

x = N.prime_division
x_primes_h = x.to_h
x_primes_h.default = 0
max_n = ans = 0

(1...N).each{|i|
  y = i.prime_division
  common_divisor = y.map{|k, v|
    [x_primes_h[k], v].min
  }.sum
  if common_divisor >= K
    y_n = y.inject(1){|r, (_, v)| r * (v + 1) }
    if y_n > max_n
      max_n = y_n
      ans = i
    end
  end
}
p ans
0