結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
![]() |
提出日時 | 2025-03-18 04:15:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,133 ms / 3,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 228,356 KB |
最終ジャッジ日時 | 2025-03-18 05:24:37 |
合計ジャッジ時間 | 24,971 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
class BIT: def query(self, m): res = 0 while m > 0: res += self.bit[m] m -= m&(-m) return res def sum(self, a, b): return self.query(b)-self.query(a) def sumall(self): bitlen = self.bitlen-1 return self.query(bitlen) def add(self, m, x): m += 1 bitlen = len(self.bit) while m <= bitlen-1: self.bit[m] += x m += m&(-m) return def search(self, a): tmpsum = 0 i = 0 k = (self.bitlen-1).bit_length() while k >= 0: tmpk = 2**k if i+tmpk <= self.bitlen-1: if tmpsum+self.bit[i+tmpk] < a: tmpsum += self.bit[i+tmpk] i += tmpk k = k-1 return i+1 def __init__(self, a): self.bitlen = a+1 self.bit = [0]*(a+1) mx = 10 ** 6 xp = [0] * (mx + 1) bc = [[] for i in range(mx + 1)] for i in range(1, mx+1): for j in range(2*i, mx+1, i): xp[j] = i for i in range(1, mx+1): bc[xp[i]].append(i) Q = int(input()) bc_q = [[] for i in range(mx+1)] for i in range(Q): L, R = map(int,input().split()) bc_q[L].append((R, i)) bit = BIT(mx+1) ans = [0] * Q for i in range(mx+1): for r, c in bc_q[i]: ans[c] = bit.sum(i, r + 1) for j in bc[i]: bit.add(j, 1) print(*ans, sep = '\n')