結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー sasa8uyauya
提出日時 2025-04-12 00:22:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 922 ms / 3,000 ms
コード長 781 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 153,356 KB
最終ジャッジ日時 2025-04-12 00:22:46
合計ジャッジ時間 19,890 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class FenwickTree:
  def __init__(self, size):
    self.n = size
    self.tree = [0] * (self.n + 1)
  
  def add(self, index, delta):
    index += 1
    while index <= self.n:
      self.tree[index] += delta
      index += index & -index
  
  def sum(self, index):
    index += 1
    res = 0
    while index > 0:
      res += self.tree[index]
      index -= index & -index
    return res


L=10**6
f=[0]*(L+1)
for i in range(1,L+1):
  for j in range(i+i,L+1,i):
    f[j]=i

q=[[] for i in range(L+1)]
Q=int(input())
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  if l==1:
    ans[i]=1
  else:
    q[r]+=[(l,i)]

st=FenwickTree(L+2)
for r in range(2,L+1):
  p2,p1=f[r],r
  st.add(p2+1,1)
  st.add(p1+1,-1)
  for l,i in q[r]:
    ans[i]=st.sum(l)

print(*ans,sep="\n")
0