結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:14:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,409 ms / 3,000 ms |
コード長 | 1,039 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 138,088 KB |
最終ジャッジ日時 | 2025-04-11 22:15:11 |
合計ジャッジ時間 | 22,105 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
class BIT: ini = 0 def __init__(s, num): s.N = 1 while s.N <= num: s.N *= 2 s.T = [s.ini] * s.N def set(s, L): for i in range(len(L)): s.update(i, L[i]) def update(s, x, n): # xをnにする k = x + 1 s.T[k - 1] += n k += k & -k while k <= s.N: s.T[k - 1] += n k += k & -k def getV(s, x): # xまでの和(x含む) if x < 0: return 0 x += 1 ans = s.T[x - 1] x -= x & -x while x != 0: ans += s.T[x - 1] x -= x & -x return ans Q = int(input()) LR = [list(map(int, input().split())) for _ in range(Q)] N = 10 ** 6 + 1 seg = BIT(N) LRI = [[LR[i][0], LR[i][1], i] for i in range(Q)] LRI.sort(reverse = True) ans = [0] * Q re = N T = [0] * N for l, r, i in LRI: if l == 1: ans[i] = 1 continue for n in range(l, re): if T[n]: continue for j in range(n + n, N, n): if T[j] == 0: seg.update(j, 1) T[j] = 1 re = l a = seg.getV(r) - seg.getV(l - 1) ans[i] = r - l + 1 - a for a in ans: print(a)