結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 potato167
提出日時 2025-04-12 00:02:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 577 ms / 3,000 ms
コード長 3,373 bytes
コンパイル時間 2,761 ms
コンパイル使用メモリ 210,752 KB
実行使用メモリ 104,156 KB
最終ジャッジ日時 2025-04-12 00:02:38
合計ジャッジ時間 24,944 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 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;

int input(){
    int x = 0;
    char c;
    while ((c = getchar_unlocked() ^ 48) < 10){
        x = x * 10 + c;
    }
    return x;
}


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<int> len_sum(N + 1);
    vector<int> div, pos;
    rep(i, 0, N){
        for (auto x : table[A[i]]) pos.push_back(i), div.push_back(x);
        len_sum[i + 1] = len_sum[i] + (int)table[A[i]].size();
    }
    int LS = len_sum[N];
    vector<int> left(LS, -1), right(LS, LS);
    vector<int> front(B, -1);
    rep(i, 0, LS){
        if (front[div[i]] != -1){
            left[i] = front[div[i]];
            right[front[div[i]]] = i;
        }
        front[div[i]] = i;
    }
    const int D = 64;
    int len = (N + D - 1) / D;
    vector<mint> dp(len + 1, 1);
    vector<mint> save;
    vector<int> divD(N + 1);
    save.reserve((len + 1) * len);
    rep(i, 0, N + 1) divD[i] = i / D;
    rep(i, 0, LS) if (left[i] == -1){
        dp[divD[pos[i]] + 1] *= table[div[i]][0];
    }
    rep(i, 0, N){
        if (i % D == 0){
            for (auto x : dp) save.push_back(x);
        }
        rep(j, len_sum[i], len_sum[i + 1]){
            if (right[j] != LS){
                dp[divD[pos[right[j]]] + 1] *= table[div[j]][0];
            }
        }
    }
    rep(i, 0, len){
        rep(j, 0, i + 1) save[i * (len + 1) + j] = 1;
        rep(j, 0, len) save[i * (len + 1) + j + 1] *= save[i * (len + 1) + 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 (divD[L] == divD[R]){
            rep(j, len_sum[L], len_sum[R]){
                if (left[j] < len_sum[L]){
                    tmp *= table[div[j]][0];
                }
            }
        }
        else{
            tmp = save[(divD[L] + 1) * (len + 1) + divD[R]];
            rep(j, len_sum[divD[R] * D], len_sum[R]){
                if (left[j] < len_sum[L]){
                    tmp *= table[div[j]][0];
                }
            }
            int r = len_sum[divD[R] * D];
            rep(j, len_sum[L], len_sum[(divD[L] + 1) * D]){
                if (r <= right[j]){
                    tmp *= table[div[j]][0];
                }
            }
        }

        ans.push_back(tmp);
        F = tmp;
    }
    return ans;
}

int main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N = input();
    vector<int> A(N);
    rep(i, 0, N){
    	A[i] = input();
    }
    int Q = input();
    vector<ll> a(Q), b(Q);
    rep(i, 0, Q){
    	a[i] = input();
    	b[i] = input();
    }
    auto ans = solve_on(N, A, Q, a, b);
    for (auto x : ans){
        cout << x.val() << "\n";
    }
}
0