結果

問題 No.3026 Range LCM (Online Version)
ユーザー Vincent Shaw
提出日時 2025-02-14 21:58:53
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,443 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 404,820 KB
最終ジャッジ日時 2025-02-14 22:04:31
合計ジャッジ時間 120,257 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = len(l1)
    len2 = 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] の素因数分解結果を入れる）
def build_seg(arr):
    n = len(arr)
    size = 1
    while size < n:
        size *= 2
    seg = [None]*(2*size)
    # 葉 (インデックス size～size+n-1)
    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]
    # maxA <= 200000 なので，spf のサイズは 200001 程度
    spf = build_spf(maxA)
    # 各 A[i] の素因数分解結果をリストにまとめる
    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 = []
    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
        # 区間 [L,R] (1-index) → [L-1, R-1] (0-index)
        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