結果

問題 No.2039 Copy and Avoid
ユーザー tomerun
提出日時 2022-08-12 23:14:13
言語 Crystal
(1.14.0)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 914 bytes
コンパイル時間 13,941 ms
コンパイル使用メモリ 297,756 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 03:53:34
合計ジャッジ時間 14,991 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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