結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-02-11 04:54:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,661 bytes
コンパイル時間 2,673 ms
コンパイル使用メモリ 210,932 KB
実行使用メモリ 41,280 KB
最終ジャッジ日時 2025-02-14 01:43:28
合計ジャッジ時間 23,033 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(p) (p).begin(),(p).end()
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <atcoder/segtree>
mint op(mint a, mint b){
    return a * b;
}
mint e(){
    return 1;
}
vector<mint> solve_off(int N, vector<int> A, int Q, vector<int> L, vector<int> R){
    const int B = 200'200;
    vector<vector<int>> table(B);
    rep(i, 2, B) if (table[i].empty()){
        ll tmp = i;
        while (tmp < B){
            for (int j = tmp; j < B; j += tmp){
                table[j].push_back(tmp);
            }
            tmp *= i;
        }
    }
    vector<vector<int>> G(B);
    vector<int> ind(B);
    atcoder::segtree<mint, op, e> seg(N);
    rep(i, 0, N){
        int tmp = 1;
        for (auto x : table[A[i]]){
            if (G[x].empty()){
                tmp *= table[x].front();
            }
            G[x].push_back(i);
        }
        seg.set(i, tmp);
    }
    rep(i, 0, Q) L[i]--;
    vector<int> order(Q);
    rep(i, 0, Q) order[i] = i;
    sort(all(order), [&](int l, int r){
        return L[l] < L[r];
    });
    vector<mint> ans(Q);
    int l = 0;
    for (auto id : order){
        while (l < L[id]){
            for (auto x : table[A[l]]){
                ind[x]++;
                if (ind[x] < (int)G[x].size()){
                    int a = G[x][ind[x]];
                    seg.set(a, seg.get(a) * table[x].front());
                }
            }
            l++;
        }
        ans[id] = seg.prod(L[id], R[id]);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    int Q;
    cin >> Q;
    vector<int> L(Q), R(Q);
    rep(i, 0, Q) cin >> L[i] >> R[i];
    auto ans = solve_off(N, A, Q, L, R);
    for (auto x : ans){
        cout << x.val() << "\n";
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0