結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-02-13 21:56:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 822 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 202,504 KB
最終ジャッジ日時 2025-02-14 01:45:42
合計ジャッジ時間 99,369 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def lcm(a: int, b: int) -> int:
    return a // math.gcd(a, b) * b  # 乗算前に割ることでオーバーフローを防ぐ
size = (1 << 18)
N = int(input())
A = list(map(int, input().split()))
seg = [1] * (size * 2)
for i in range(N):
    seg[i + size] = A[i]
for i in range(size - 1, 0, -1):
    seg[i] = lcm(seg[i * 2], seg[i * 2 + 1])
Q = int(input())
F = 1
MOD = 998244353
for i in range(Q):
    a, b = map(int, input().split())
    l = a * F % MOD
    r = b * F % MOD
    l %= N
    r %= N
    if l > r:
        l, r = r, l
    r += 1
    l += size
    r += size
    res = 1
    while l < r:
        if l & 1:
            res = lcm(res, seg[l])
            l += 1
        if r & 1:
            r -= 1
            res = lcm(res, seg[r])
        l //= 2
        r //= 2
    F = res % MOD
    print(F)
0