結果

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

ソースコード

diff #
raw source code 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        assert 0 <= i < self.n
        i = i+1
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def set(self, i, x):
        assert 0 <= i <= self.n
        self.add(i,x-self.get(i))
    def get(self, i, j=None):# j=Noneのときiを取得, [i, j)の和を取得
        if j is None:
            return self.el[i+1]
        return self.sum(j) - self.sum(i)
    def lower_bound(self, x):#a[0]+a[1]+...+a[k]>xなる最小のkを求める
        if x < 0:
            return -1
        else:
            k = 0
            r = 1
            size = r
            while r < self.n:r <<= 1
            while size:
                if k + size < self.n and bit.data[k+size] < x:
                    x -= bit.data[k+size]
                    k += size
            return k
q = ni()
# m = 21
m = 10 ** 6 + 10
g = [[] for i in range(m)]
for i in range(q):
    l, r = na()
    g[l].append((r, i))


# l = 1 1
# l = 2 

# x が食べらない = l <= y < x and y divide x なる y が存在
ans = [-1] * q
a = [1] * m
bit = BIT(m)
for i in range(1, m):
    bit.add(i, 1)

for i in range(m-1, 0, -1):
    for j in range(i * 2, m, i):
        if a[j] == 1:
            a[j] = 0
            bit.add(j, -1)
    # print(a)
    for r, j in g[i]:
        ans[j] = bit.get(i, r + 1)

for i in range(q):
    print(ans[i])
0