結果

問題 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,772 ms
コンパイル使用メモリ 210,028 KB
実行使用メモリ 41,272 KB
最終ジャッジ日時 2025-09-06 00:37:55
合計ジャッジ時間 26,673 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other WA * 1 RE * 36
権限があれば一括ダウンロードができます

ソースコード

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";
    }
}
0