わからないので解説見ました。
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