結果

問題 No.2039 Copy and Avoid
ユーザー tomeruntomerun
提出日時 2022-08-12 23:14:13
言語 Crystal
(1.11.2)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 914 bytes
コンパイル時間 15,390 ms
コンパイル使用メモリ 295,516 KB
実行使用メモリ 4,328 KB
最終ジャッジ日時 2023-10-24 11:34:15
合計ジャッジ時間 15,656 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
4,324 KB
testcase_01 AC 1 ms
4,328 KB
testcase_02 AC 3 ms
4,328 KB
testcase_03 AC 2 ms
4,328 KB
testcase_04 AC 1 ms
4,328 KB
testcase_05 AC 4 ms
4,328 KB
testcase_06 AC 1 ms
4,328 KB
testcase_07 AC 1 ms
4,328 KB
testcase_08 AC 1 ms
4,328 KB
testcase_09 AC 1 ms
4,328 KB
testcase_10 AC 2 ms
4,328 KB
testcase_11 AC 1 ms
4,328 KB
testcase_12 AC 2 ms
4,328 KB
testcase_13 AC 51 ms
4,328 KB
testcase_14 AC 53 ms
4,328 KB
testcase_15 AC 51 ms
4,328 KB
testcase_16 AC 49 ms
4,328 KB
testcase_17 AC 3 ms
4,328 KB
testcase_18 AC 4 ms
4,328 KB
testcase_19 AC 3 ms
4,328 KB
testcase_20 AC 6 ms
4,328 KB
testcase_21 AC 2 ms
4,328 KB
testcase_22 AC 2 ms
4,328 KB
testcase_23 AC 2 ms
4,328 KB
testcase_24 AC 1 ms
4,328 KB
testcase_25 AC 1 ms
4,328 KB
testcase_26 AC 1 ms
4,328 KB
testcase_27 AC 3 ms
4,328 KB
testcase_28 AC 1 ms
4,328 KB
testcase_29 AC 1 ms
4,328 KB
testcase_30 AC 2 ms
4,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = 1i64 << 60
n, m, a32, b32 = read_line.split.map(&.to_i)
a = a32.to_i64
b = b32.to_i64
c = read_line.split.map(&.to_i).to_set
divs = [1]
d = 2i64
while d * d <= n
  if n % d == 0
    divs << d.to_i
    divs << n // d if d * d != n
  end
  d += 1
end
oks = {n => 0i64}
divs.sort.reverse_each do |d|
  cs = c.select { |v| v % d == 0 }
  max = (cs.empty? ? n : cs.min) // d
  cn = n // d
  best = INF
  if cs.empty?
    best = (d == 1 ? 0i64 : b) + a * (cn - 1)
  end
  cd = 2i64
  while cd * cd <= cn && cd < max
    if cn % cd == 0
      if oks.has_key?(d * cd)
        best = {best, oks[d * cd] + (d == 1 ? 0i64 : b) + a * (cd - 1)}.min
      end
      if cn // cd < max && oks.has_key?(d * (cn // cd))
        best = {best, oks[d * (cn // cd)] + (d == 1 ? 0i64 : b) + a * (cn // cd - 1)}.min
      end
    end
    cd += 1
  end
  if best != INF
    oks[d] = best
  end
end
puts oks.has_key?(1) ? oks[1] : -1
0