結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-02-13 23:11:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,033 ms / 3,000 ms
コード長 3,270 bytes
コンパイル時間 4,222 ms
コンパイル使用メモリ 296,540 KB
実行使用メモリ 126,728 KB
最終ジャッジ日時 2025-02-14 01:45:05
合計ジャッジ時間 30,180 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 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;


vector<mint> solve_on(int N, vector<int> &A, int Q, vector<ll> &a, vector<ll> &b){
	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>> left(N), right(N);
    vector<pair<int, int>> front(B, {-1, -1});
    rep(i, 0, N){
        int j = 0;
        for (auto x : table[A[i]]){
            if (front[x].first == -1){
                left[i].push_back(-1);
            }
            else{
                left[i].push_back(front[x].first);
                right[front[x].first][front[x].second] = i;
            }
            front[x] = {i, j};
            right[i].push_back(N);
            j++;
        }
    }
    const int D = 64;
    int len = (N + D - 1) / D;
    vector<mint> dp(len, 1);
    vector<vector<mint>> save;
    vector<int> div(N + 1);
    rep(i, 0, N + 1) div[i] = i / D;
    rep(i, 0, N) rep(j, 0, table[A[i]].size()){
        if (left[i][j] == -1){
            dp[div[i]] *= table[table[A[i]][j]][0];
        }
    }
    rep(i, 0, N){
        if (i % D == 0){
            save.push_back(dp);
        }
        rep(j, 0, table[A[i]].size()){
            if (right[i][j] != N){
                dp[div[right[i][j]]] *= table[table[A[i]][j]][0];
            }
        }
    }
    rep(i, 0, save.size()){
        save[i].insert(save[i].begin(), 1);
        rep(j, 0, i) save[i][j + 1] = 1;
        rep(j, 0, len) save[i][j + 1] *= save[i][j];
    }
    vector<mint> ans;
    mint F = 1;
    rep(id, 0, Q){
        mint a1 = F * a[id];
        mint b1 = F * b[id];
        int L = a1.val() % N + 1;
        int R = b1.val() % N + 1;
        // hide rule
        {
            if ((a[id] + b[id]) & 4){
                swap(L, R);
            }
            assert(L <= R);
        }
        L--;
        mint tmp = 1;

        if (L / D == div[R]){
            rep(i, L, R) rep(j, 0, table[A[i]].size()){
                if (left[i][j] < L){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
        }
        else{
            tmp = save[div[L] + 1][div[R]];
            rep(i, div[R] * D, R) rep(j, 0, table[A[i]].size()){
                if (left[i][j] < L){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
            int r = (R / D) * D;
            for (int i = (div[L] + 1) * D - 1; i >= L; i--) rep(j, 0, table[A[i]].size()){
                if (r <= right[i][j]){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
        }

        ans.push_back(tmp);
        F = tmp;
    }
    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<ll> a(Q), b(Q);
    rep(i, 0, Q) cin >> a[i] >> b[i];
    auto ans = solve_on(N, A, Q, a, b);
    for (auto x : ans){
        cout << x.val() << "\n";
    }
}
0