結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー Yotugi
提出日時 2025-05-14 23:04:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,988 ms / 3,000 ms
コード長 2,589 bytes
コンパイル時間 653 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 162,084 KB
最終ジャッジ日時 2025-05-14 23:05:16
合計ジャッジ時間 32,336 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin,setrecursionlimit#,set_int_max_str_digits
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
setrecursionlimit(20000000) # これこどふぉだと無理
#set_int_max_str_digits(200010)
mod = 998244353 
ii = lambda :int(stdin.readline())
mi = lambda :map(int,stdin.readline().split())
li = lambda :list(mi())
gmi = lambda :map(lambda x: int(x) - 1, stdin.readline().split())
gi = lambda :list(map(lambda x: 0 if x == "." else 1,input())) # グリッド入力受け取り
py = lambda :print("Yes")
pn = lambda :print("No")
pf = lambda :print("First") 
ps = lambda :print("Second")
vec = [(1,0),(-1,0),(0,-1),(0,1)]
vec1 = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] #8方向
inf = 2*10**18


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):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j = None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

    #合計値がsを超える最小のインデックス
    def lowerbound(self, s):
        x = 0
        y = 0
        for i in range(self.n.bit_length(), -1, -1):
            k = x + (1 << i)
            if k <= self.n and (y + self.data[k] < s):
                y += self.data[k]
                x += 1 << i
        return x + 1
    
    def show(self):
        print(self.el[1::])



N = 10**6# 適当な値を入れる、WAが出るなら脳死で10**6とかを入れた方がいい

p_data = [-1]*(N+1) # 素数なら 1、素数でないなら最大の素因数 

p_data[1] = 1
for i in range(2,N+1):
    if p_data[i] == -1:
        p_data[i] = 1
    for j in range(2*i,N+1,i):
        p_data[j] = i 

Q = ii() 
q = []
for i in range(Q):
    l,r = mi() 
    q.append([l-1,l-1,i])
    q.append([r,l-1,i])

q.sort(reverse=True)
fw = BIT(N+5) 

ans = [0]*Q
tmp = 0 

#print(p_data)
for i in range(N+1):
    # if p_data[i] == 0:
    #     tmp += 1 
    # else:
    if i:
        fw.add(p_data[i],1)
    while q[-1][0] == i:
        x,k,pos = q.pop() 
        tmp = fw.sum(k)

        if x == k:
            ans[pos] -= tmp 
        else:
            ans[pos] += tmp
        if not q:
            break 

    else:
        continue 
    break 

for i in range(Q):
    if ans[i] == 0:
        ans[i] = 1 
print(*ans,sep="\n")
0