結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー 学ぶマン
提出日時 2025-04-12 16:42:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,360 ms / 3,000 ms
コード長 2,410 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 273,532 KB
最終ジャッジ日時 2025-04-12 16:43:20
合計ジャッジ時間 25,263 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, math, typing
sys.setrecursionlimit(10**8)
sys.set_int_max_str_digits(0)
INF = 10**18
MOD = 998244353
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import product, combinations, permutations, groupby, accumulate
from heapq import heapify, heappop, heappush
def I():   return sys.stdin.readline().rstrip()
def II():  return int(sys.stdin.readline().rstrip())
def IS():  return sys.stdin.readline().rstrip().split()
def MII(): return map(int, sys.stdin.readline().rstrip().split())
def LI():  return list(sys.stdin.readline().rstrip())
def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split()))
def LII(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LSI(): return list(map(str, sys.stdin.readline().rstrip().split()))
def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
def kiriage(a, b): return (a+b-1)//b

class FenwickTree:
    '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree'''

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        return self._sum(right) - self._sum(left)

    def _sum(self, r: int) -> typing.Any:
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r

        return s

Q = II()
limit = 10**6
ans_dd = defaultdict(list)
query = []
for i in range(Q):
    l, r = MII()
    query.append((l, r))
    ans_dd[l].append(i)

A = [1] * (limit + 1) # 0 ~ limit
A[0] = 0
ft = FenwickTree(limit + 1)

# 初期値を1にする
for i in range(1, limit + 1):
    ft.add(i, 1)

ans = [-1] * Q

for l in range(limit, 0, -1):
    # l の倍数を消す
    for num in range(2*l, limit + 1, l):
        if num > limit:
            break
        if A[num] == 1: # まだ 1 が立ってたら0にする
            A[num] = 0
            ft.add(num, -1)

    # l のクエリに回答する
    for ansid in ans_dd[l]:
        l, r = query[ansid]
        # [l, r] の区間で 1 で残ってる整数のカウント
        ans[ansid] = ft.sum(l, r + 1)

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