結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー titia
提出日時 2025-04-12 03:54:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 925 ms / 3,000 ms
コード長 1,217 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 244,160 KB
最終ジャッジ日時 2025-04-12 03:54:33
合計ジャッジ時間 20,443 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

LIST=[1]*1000020

for i in range(2,1000020):
    for j in range(i+i,1000020,i):
        LIST[j]=i

TO=[[] for i in range(1000020)]

for i in range(2,1000001):
    TO[LIST[i]+1].append(i)

# BIT(BIT-indexed tree)
LEN=1000020

BIT=[0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ
    return ANS


Q=int(input())

QU=[list(map(int,input().split()))+[i] for i in range(Q)]
ANS=[0]*Q

LL=[[] for i in range(LEN+1)]

for x,y,ind in QU:
    LL[x].append((y,ind))


for i in range(1,LEN):

    if i>=2:
        for k in TO[i]:
            update(k,1)

    for y,ind in LL[i]:
        if i==1:
            ANS[ind]=1
        else:
            ANS[ind]=getvalue(y)-getvalue(i-1)
            
print("\n".join(map(str,ANS)))
0