結果

問題 No.3026 Range LCM (Online Version)
コンテスト
ユーザー Vincent Shaw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0