結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-02-14 00:57:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,458 ms / 3,000 ms
コード長 2,169 bytes
コンパイル時間 1,160 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 399,936 KB
最終ジャッジ日時 2025-02-14 02:15:21
合計ジャッジ時間 38,776 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
a = [0] * Q
b = [0] * Q
for i in range(Q):
    a[i], b[i] = map(int, input().split())
lim = 200001
table = [[] for _ in range(lim)]
for i in range(2, lim):
    if len(table[i]) == 0:
        tmp = i
        while tmp < lim:
            j = tmp
            while j < lim:
                table[j].append(tmp)
                j += tmp
            tmp *= i

div = []
pos = []
len_sum = [0] * (N + 1)
for i in range(N):
    len_sum[i + 1] = len_sum[i]
    for x in table[A[i]]:
        div.append(x)
        pos.append(i)
        len_sum[i + 1] += 1
LS = len_sum[-1]
lef = [-1] * LS
rig = [LS] * LS
fr = [-1] * lim
for i in range(LS):
    if fr[div[i]] != -1:
        lef[i] = fr[div[i]]
        rig[fr[div[i]]] = i
    fr[div[i]] = i
D = 100
ND = (N + D - 1) // D
dp = [1] * (ND + 1)
save = []
ind = 0
for i in range(LS):
    if lef[i] == -1:
        x = pos[i] // D + 1
        dp[x] = dp[x] * table[div[i]][0] % MOD
while ind < N:
    n_ind = min(ind + D, N)
    th = ind // D
    for j in range(0, ND + 1):
        if j <= th:
            save.append(1)
        else:
            save.append(save[-1] * dp[j] % MOD)
    for i in range(len_sum[ind], len_sum[n_ind]):
        if rig[i] != LS:
            x = pos[rig[i]] // D + 1
            dp[x] = dp[x] * table[div[i]][0] % MOD
    ind = n_ind
ans = 1
for rp in range(Q):
    L = ans * a[rp] % MOD
    R = ans * b[rp] % MOD
    L %= N
    R %= N
    if L > R:
        L, R = R, L
    R += 1
    ans = 1
    if L // D == R // D:
        for i in range(len_sum[L], len_sum[R]):
            if len_sum[R] <= rig[i]:
                ans = ans * table[div[i]][0] % MOD
    else:
        ans = save[(ND + 1) * (L // D + 1) + R // D]
        l = len_sum[(L // D + 1) * D]
        for i in range(len_sum[(R // D) * D], len_sum[R]):
            if lef[i] < l:
                ans = ans * table[div[i]][0] % MOD
        r = len_sum[R]
        for i in range(len_sum[L], len_sum[(L // D) * D + D]):
            if r <= rig[i]:
                ans = ans * table[div[i]][0] % MOD
    print(ans, flush=False)
0