結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-02-11 05:57:05
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,572 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 214,976 KB
最終ジャッジ日時 2025-02-14 01:43:07
合計ジャッジ時間 23,238 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
MOD = 998244353
N = int(input())
A = [i for i in map(int, input().split())]
Q = int(input())
L = [0] * Q
R = [0] * Q
for i in range(Q):
    L[i], R[i] = map(int, input().split())
    L[i] -= 1
B = 200200
table = [0] * B
for i in range(2, B):
    if table[i] == 0:
        j = i
        while j < B:
            table[j] = i
            j += i
ans = [0] * Q
G = [[] for i in range(B)]
div = [[] for i in range(N)]
ind = [0] * B
for i in range(N):
    id = 0
    val = A[i]
    p = -1
    m = 1
    while val != 1:
        if p != table[val]:
            p = table[val]
            m = 1
        m *= p
        G[m].append(i)
        id += 1
        val //= p
        div[i].append(m)
size = 1
while size < N: size *= 2
seg = [1] * (size * 2)
def mul_seg(id, val):
    id += size
    seg[id] *= val
    while id != 1:
        id //= 2
        seg[id] = seg[id * 2] * seg[id * 2 + 1] % MOD
def prod(l, r):
    l += size
    r += size
    res = 1
    while l < r:
        if l & 1:
            res = res * seg[l] % MOD
            l += 1
        if r & 1:
            r -= 1
            res = res * seg[r] % MOD
        l //= 2
        r //= 2
    return res
order = list(range(Q))
order.sort(key=lambda i : L[i])
l = 0
for i in range(B):
    if len(G[i]): mul_seg(G[i][0], table[i])
for id in order:
    while l < L[id]:
        for a in div[l]:
            ind[a] += 1
            if len(G[a]) != ind[a]:
                mul_seg(G[a][ind[a]], table[a])
        l += 1
    ans[id] = prod(L[id], R[id])
for x in ans: print(x, flush=False)
0