結果

問題 No.811 約数の個数の最大化
ユーザー letrangerjp
提出日時 2019-04-12 21:56:26
言語 Ruby
(ruby 2.5.3p57)
結果
AC  
実行時間 798 ms
コード長 379 Byte
コンパイル時間 16 ms
使用メモリ 8,912 KB
最終ジャッジ日時 2019-07-03 12:23:17

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample_1 AC 13 ms
6,868 KB
sample_2 AC 17 ms
6,872 KB
sample_3 AC 699 ms
6,868 KB
testcase_1 AC 13 ms
8,912 KB
testcase_2 AC 14 ms
6,868 KB
testcase_3 AC 24 ms
6,872 KB
testcase_4 AC 53 ms
6,872 KB
testcase_5 AC 74 ms
6,868 KB
testcase_6 AC 319 ms
6,872 KB
testcase_7 AC 341 ms
6,872 KB
testcase_8 AC 215 ms
6,872 KB
testcase_9 AC 694 ms
6,868 KB
testcase_10 AC 170 ms
6,868 KB
testcase_11 AC 798 ms
6,868 KB
testcase_12 AC 795 ms
6,868 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