結果

問題 No.6 使いものにならないハッシュ
ユーザー vjudge1
提出日時 2025-09-04 17:12:12
言語 Crystal
(1.14.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 724 bytes
コンパイル時間 14,390 ms
コンパイル使用メモリ 309,252 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-04 17:12:28
合計ジャッジ時間 13,991 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def digital_root(n : Int32) : Int32
  n == 0 ? 0 : 1 + (n - 1) % 9
end

# Read k and n from separate lines
k = gets.not_nil!.to_i
n = gets.not_nil!.to_i

# Sieve of Eratosthenes
is_prime = Array.new(n + 1, true)
primes = [] of Int32

(2..n).each do |i|
  if !is_prime[i]
    next
  end
  
  primes << i if k <= i
  j = i * 2
  while j <= n
    is_prime[j] = false
    j += i
  end
end

# Process primes with sliding window
que = Deque(Int32).new
v = Array.new(10, false)
mlen = 0
ans = 0

primes.each do |p|
  t = digital_root(p)
  
  while v[t]
    front = que.shift
    v[digital_root(front)] = false
  end
  
  que.push(p)
  v[t] = true
  
  if mlen <= que.size
    mlen = que.size
    ans = que.first
  end
end

puts ans
0