結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー nasutarou1341
提出日時 2025-04-11 22:14:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,409 ms / 3,000 ms
コード長 1,039 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 138,088 KB
最終ジャッジ日時 2025-04-11 22:15:11
合計ジャッジ時間 22,105 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xをnにする
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

N = 10 ** 6 + 1
seg = BIT(N)

LRI = [[LR[i][0], LR[i][1], i] for i in range(Q)]
LRI.sort(reverse = True)

ans = [0] * Q
re = N
T = [0] * N
for l, r, i in LRI:
  if l == 1:
    ans[i] = 1
    continue
  for n in range(l, re):
    if T[n]: continue
    for j in range(n + n, N, n):
      if T[j] == 0:
        seg.update(j, 1)
        T[j] = 1
  re = l
  a = seg.getV(r) - seg.getV(l - 1)
  ans[i] = r - l + 1 - a

for a in ans:
  print(a)
0