更新日時で差をつけろ

差をつけられそう

AOJ-ICPC 200点: 竹の花

わからないので解説見ました。
ACM-ICPC 2016 国内予選 C: 竹の花 · うさぎ小屋
わかりやすい。

loop do
  m, n = gets.split.map(&:to_i)
  break if m == 0

  nxt = m
  used = []
  n.times do |i|
    a = nxt
    while a <= 7368791
      used[a] = true
      a += nxt
    end

    loop do
      nxt += 1
      break unless used[nxt]
    end
  end

  puts nxt
end


こう書くとm=2, n=500000のケースが間に合いません。上の方が速いしシンプル。

loop do
  m, n = gets.split.map(&:to_i)
  break if m == 0

  nxt = m
  years = []
  n.times do |i|
    years << nxt

    loop do
      nxt += 1
      f = false
      years.each do |r|
        f = true if nxt % r == 0 # それよりも短い周期で割り切れたら追加しない
      end
      break unless f
    end
  end

  m.upto(7368791) do |i|
    found = false
    years.each do |y|
      if i % y == 0
        found = true
        break
      end
    end

    unless found
      puts i
      break
    end
  end
end