結果

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

ソースコード

diff #
raw source code 

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
Z=Bit(10**6+1)
Q=int(input())
v=[0]*(10**6+1)
for x in range(1,10**6):
  for y in range(2,10**6+1):
    if x*y>10**6:
      break
    v[x*y]=x
pos=0
result=[0]*Q
L=[]
for i in range(Q):
  l,r=map(int,input().split())
  L.append((r,l,i))
L.sort()
for i in range(Q):
  r,l,e=L[i][:]
  for y in range(pos+1,r+1):
    Z.add(v[y]+1,1)
  pos=r
  ans=Z.sum(l)-(l-1)
  result[e]=ans
for i in range(Q):
  print(result[i])
0