結果

問題 No.3461 Min GCD
コンテスト
ユーザー tomerun
提出日時 2026-02-28 14:43:29
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
AC  
実行時間 1,347 ms / 2,000 ms
コード長 743 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,861 ms
コンパイル使用メモリ 342,332 KB
実行使用メモリ 447,880 KB
最終ジャッジ日時 2026-02-28 14:43:55
合計ジャッジ時間 23,985 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, k = read_line.split.map(&.to_i64)
a = read_line.split.map(&.to_i)
b = read_line.split.map(&.to_i)
cnt = Array.new(n) do |i|
  divs = [] of Int32
  d = 1
  while d * d < a[i]
    if a[i] % d == 0
      divs << d << a[i] // d
    end
    d += 1
  end
  if d * d == a[i]
    divs << d
  end
  c = [] of Tuple(Int32, Int64)
  divs.sort.each do |d|
    rem = b[i] % d
    use = rem == 0 ? 0 : d - rem
    while c.size > 0 && c[-1][1] >= use
      c.pop
    end
    c << {d, use.to_i64}
  end
  c
end
lo = 1
hi = a.min + 1
while hi - lo > 1
  mid = (lo + hi) // 2
  need = n.times.sum do |i|
    idx = cnt[i].bsearch_index { |x, _| x[0] >= mid }.not_nil!
    cnt[i][idx][1]
  end
  if need <= k
    lo = mid
  else
    hi = mid
  end
end
puts lo
0