結果
問題 |
No.3026 Range LCM (Online Version)
|
ユーザー |
|
提出日時 | 2025-02-14 21:59:41 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,766 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 404,736 KB |
最終ジャッジ日時 | 2025-02-14 22:06:19 |
合計ジャッジ時間 | 120,343 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 26 |
ソースコード
import sys, math from array import array sys.setrecursionlimit(3000000) MOD = 998244353 # 最小素因数表(spf)を array('I') を用いて構築 def build_spf(n): spf = array('I', (i for i in range(n+1))) r = int(n**0.5) for i in range(2, r+1): if spf[i] == i: for j in range(i*i, n+1, i): if spf[j] == j: spf[j] = i return spf # x の素因数分解:昇順に (p, exp) のリストを返す def factorize(x, spf): res = [] while x != 1: p = spf[x] cnt = 0 while x % p == 0: x //= p cnt += 1 res.append((p, cnt)) return res # 2 つの素因数リスト(昇順の (p, exp))のマージ: # 各素数について指数は「最大値」を取る def merge_factors(l1, l2): i = j = 0 res = [] len1, len2 = len(l1), len(l2) while i < len1 and j < len2: p1, e1 = l1[i] p2, e2 = l2[j] if p1 == p2: res.append((p1, e1 if e1>e2 else e2)) i += 1 j += 1 elif p1 < p2: res.append((p1, e1)) i += 1 else: res.append((p2, e2)) j += 1 while i < len1: res.append(l1[i]) i += 1 while j < len2: res.append(l2[j]) j += 1 return res # セグメント木構築 # 葉には各 A[i] の素因数分解リスト(昇順の (p,exp))を入れる def build_seg(arr): n = len(arr) size = 1 while size < n: size *= 2 seg = [None]*(2*size) for i in range(n): seg[size+i] = arr[i] for i in range(n, size): seg[size+i] = [] # 単位元(空リスト) for i in range(size-1, 0, -1): seg[i] = merge_factors(seg[2*i], seg[2*i+1]) return seg, size # 区間クエリ [l, r] (0-index) def query_seg(seg, size, l, r): resl = [] resr = [] l += size r += size while l <= r: if (l & 1) == 1: resl = merge_factors(resl, seg[l]) l += 1 if (r & 1) == 0: resr = merge_factors(seg[r], resr) r -= 1 l //= 2 r //= 2 return merge_factors(resl, resr) def main(): data = sys.stdin.buffer.read().split() if not data: return it = iter(data) n = int(next(it)) A = [0]*n maxA = 0 for i in range(n): A[i] = int(next(it)) if A[i] > maxA: maxA = A[i] # A[i] の最大値は 2e5 以下なので、spf のサイズは 2e5+1 spf = build_spf(maxA) # 各 A[i] の素因数分解結果(昇順の (p,exp) リスト)を配列 factorizations に保存 factorizations = [None]*n for i in range(n): factorizations[i] = factorize(A[i], spf) seg, size = build_seg(factorizations) Q = int(next(it)) prev_ans = 1 out_lines = [] # オンラインクエリ処理 # 各クエリは、まず a_i, b_i が与えられ、以下のように復元する: # x = (a_i * prev_ans) mod MOD # y = (x mod n) + 1 # z = (b_i * prev_ans) mod MOD # w = (z mod n) + 1 # L = min(y, w), R = max(y, w) for _ in range(Q): ai = int(next(it)) bi = int(next(it)) x = (ai * prev_ans) % MOD y = (x % n) + 1 z = (bi * prev_ans) % MOD w = (z % n) + 1 L = y if y < w else w R = w if y < w else y # 0-index でクエリ:[L-1, R-1] fac = query_seg(seg, size, L-1, R-1) res = 1 for p, exp in fac: res = (res * pow(p, exp, MOD)) % MOD out_lines.append(str(res)) prev_ans = res sys.stdout.write("\n".join(out_lines) + "\n") if __name__ == '__main__': main()