結果

問題 No.3026 Range LCM (Online Version)
ユーザー 👑 Nachia
提出日時 2025-02-14 22:10:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,458 ms / 3,000 ms
コード長 13,649 bytes
コンパイル時間 2,128 ms
コンパイル使用メモリ 120,780 KB
実行使用メモリ 73,296 KB
最終ジャッジ日時 2025-02-14 22:12:13
合計ジャッジ時間 42,107 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cassert>
namespace nachia{
// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}
} // namespace nachia
namespace nachia{
template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:
    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }
    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};
} // namespace nachia
namespace nachia{
struct WordsizeTree{
    using Word = unsigned long long;
    static constexpr int W = 64;
    int N;
    std::vector<std::vector<Word>> A;
    static int highBit(Word x){
        if(x == 0) return 0;
        return W-1 - __builtin_clzll(x);
    }
    static int lowBit(Word x){
        if(x == 0) return W;
        return __builtin_ctzll(x);
    }
    WordsizeTree(int length){
        N = length;
        int n = length;
        do {
            std::vector<Word> a(n/W+1,0);
            A.emplace_back(std::move(a));
            n /= W;
        } while(n);
    }
    WordsizeTree(const std::string& binStr = ""){
        N = binStr.size();
        int n = N;
        {
            std::vector<Word> a(n/W+1);
            for(int i=0; i<n; i++) if(binStr[i] == '1'){
                a[i/W] |= (Word)1 << (i%W);
            }
            A.emplace_back(std::move(a));
            n /= W;
        }
        while(n){
            std::vector<Word> a(n/W+1,0);
            for(int i=0; i<=n; i++){
                if(A.back()[i]) a[i/W] |= (Word)1 << (i%W);
            }
            A.emplace_back(std::move(a));
            n /= W;
        }
    }
    void insert(int x){
        for(auto& a : A){
            a[x/W] |= (Word)1 << (x % W);
            x /= W;
        }
    }
    void erase(int x){
        for(auto& a : A){
            a[x/W] &= ~((Word)1 << (x % W));
            if(a[x/W]) return;
            x /= W;
        }
    }
    int count(int x) const {
        return (int)((A[0][x/W] >> (x%W)) & 1);
    }
    void flip(int x){ if(count(x)) erase(x); else insert(x); }
    int noLessThan(int x) const {
        if(x < 0) x = 0;
        if(N <= x) return N;
        int d = 0, i = x;
        while(true){
            if(d >= (int)A.size()) return N;
            if(i/W >= (int)A[d].size()) return N;
            Word m = A[d][i/W] & ((~(Word)0) << (i%W));
            if(!m){ d++; i /= W; i++; }
            else{
                int to = lowBit(m);
                i = i/W*W + to;
                if(d == 0) break;
                i *= W;
                d--;
            }
        }
        return i;
    }
    int noGreaterThan(int x) const {
        if(x < 0) return -1;
        if(N <= x) x = N-1;
        int d = 0, i = x;
        while(true){
            if(i < 0) return -1;
            if(d >= (int)A.size()) return -1;
            Word m = A[d][i/W] & ~((~(Word)1) << (i%W));
            if(!m){ d++; i /= W; i--; }
            else{
                int to = highBit(m);
                i = i/W*W + to;
                if(d == 0) break;
                i *= W;
                i += W-1;
                d--;
            }
        }
        return i;
    }
};
} // namespace nachia
#include <cstdint>
namespace nachia{
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}
}
namespace nachia{
template<class PosX, class PosY>
struct TwoDRectangleQuery{
private:
struct BitVectorRank {
    using u64 = std::uint64_t;
    using u32 = std::uint32_t;
    
    std::vector<std::pair<u64, u32>> a;
    BitVectorRank(const std::vector<bool>& b = {}){
        int n = b.size();
        a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0));
        auto p = b.begin();
        u32 sum = 0;
        u64 tmp = 0;
        for(int i=0; i<=n; i+=64){
            tmp = 0;
            int maxd = std::min<int>(n - i, 64);
            for(int d=0; d<maxd; d++){
                tmp |= (u64)(*p ? 1 : 0) << d;
                ++p;
            }
            a[i/64] = std::make_pair(tmp, sum);
            sum += Popcount(tmp);
        }
    }
    std::uint32_t rank(std::uint32_t i) const {
        auto [b, s] = a[i >> 6];
        return (u32)(Popcount(b & ~(~u64(0) << (i & 63)))) + s;
    }
    bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
};
    
    int n;
    int N;
    int logN;
    std::vector<PosX> Xsorted;
    std::vector<PosY> Ysorted;
    std::vector<int> rankX;
    std::vector<std::vector<int>> Idx;
    std::vector<int> Z;
    std::vector<BitVectorRank> L;
public:
    TwoDRectangleQuery(){}
    TwoDRectangleQuery(const std::vector<std::pair<PosX, PosY>>& pos){
        n = pos.size();
        std::vector<int> sortIY(n);
        for(int i=0; i<n; i++) sortIY[i] = i;
        std::sort(sortIY.begin(),sortIY.end(),[&pos](int l,int r){ return pos[l].second<pos[r].second; });
        Ysorted.resize(n);
        for(int i=0; i<n; i++) Ysorted[i] = pos[sortIY[i]].second;
        std::vector<int> sortIX(n);
        rankX.resize(n);
        for(int i=0; i<n; i++) sortIX[i] = i;
        std::sort(sortIX.begin(),sortIX.end(),[&pos](int l,int r){ return pos[l]<pos[r]; });
        Xsorted.resize(n);
        for(int i=0; i<n; i++) Xsorted[i] = pos[sortIX[i]].first;
        for(int i=0; i<n; i++) rankX[sortIX[i]] = i;
        N = 1; logN = 0;
        while(N < n){ N *= 2; logN++; }
        Idx.assign(logN+1, std::vector<int>(n,-1));
        L.resize(logN);
        Z.resize(logN);
        for(int i=0; i<n; i++) Idx.back()[i] = sortIY[i];
        for(int i=logN-1; i>=0; i--){
            std::vector<bool> Lbuf(n,0);
            auto& preList = Idx[i+1];
            int z = ((n >> (i+1)) << i) + std::min(1<<i, (n % (2 << i)));
            Z[i] = z;
            int ai = 0, bi = z;
            for(int k=0; k<n; k++){
                bool chooseb = rankX[preList[k]] & (1<<i);
                if(!chooseb) Idx[i][ai++] = preList[k];
                else Idx[i][bi++] = preList[k];
                Lbuf[k] = !chooseb;
            }
            L[i] = BitVectorRank(Lbuf);
        }
        for(int i=0; i<n; i++) rankX[sortIY[i]] = i;
    }
 
    int getSegmentCount() const { return Idx.size(); }
    int size() const { return n; }
    int toVtx(int d, int i) const { return Idx[d][i]; }
    struct UpdatePoint{ int d, i; };
    std::vector<UpdatePoint> getUpdatePoints(int v) const {
        std::vector<UpdatePoint> res(logN+1);
        int p = rankX[v];
        int d = logN;
        while(d > 0){
            res[d] = { d,p };
            d--;
            if(L[d].get(p)) p = L[d].rank(p);
            else p = Z[d] + p - L[d].rank(p);
        }
        res[d] = {d,p};
        return res;
    }
    struct Query{ int d,l,r; };
    std::vector<Query> getRangesFromIdx(int xl, int xr, int yl, int yr) const {
        if(xl >= xr || yl >= yr) return {};
        std::vector<Query> res;
        struct Search{ int i, xa, xb, ys, yt; };
        std::vector<Search> Q;
        res.reserve((logN+1)*2);
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xl <= p.xa && p.xb <= xr){
                res.push_back({ p.i, p.ys, p.yt });
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            int xm = p.xa+(1<<p.i);
            if(xl < xm) Q.push_back({ p.i,p.xa,xm,nxs,nxt });
            if(xm < xr) Q.push_back({ p.i,xm,p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return res; 
    }
  
    std::vector<Query> getRanges(PosX xl, PosX xr, PosY yl, PosY yr) const {
        return getRangesFromIdx(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }
};
} // namespace nachia
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<i64(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;
using mint = nachia::StaticModint<998244353>;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int Z = 200000;
    vector<int> contribute(Z+1);
    vector<vector<int>> pf(Z+1);
    for(int p=2; p<=Z; p++) if(pf[p].empty()){
        for(int pp=p; ; pp*=p){
            contribute[pp] = p;
            for(int q=1; pp*q<=Z; q++){
                pf[pp*q].push_back(pp);
            }
            if(i64(pp)*p > Z) break;
        }
    }
    const int th = 16;
    int N; cin >> N;
    vector<int> A(N); rep(i,N) cin >> A[i];
    vector<nachia::WordsizeTree> fairy;
    vector<mint> cfairy;
    rep(i,Z+1) if(contribute[i] != 0 && contribute[i] < th){
        int d = fairy.size();
        fairy.push_back(nachia::WordsizeTree(N));
        rep(p,N) if(A[p] % i == 0) fairy[d].insert(p);
        cfairy.push_back(contribute[i]);
    }
    vector<pair<int,int>> points;
    vector<mint> V;
    vector<int> P(Z+1, -1);
    for(auto& a : A) for(int p=2; p<th; p++) while(a%p == 0) a/=p;
    rep(i,N){
        int a = A[i];
        for(int pp : pf[a]) if(contribute[pp] >= th){
            if(P[pp] != -1){
                points.push_back({ P[pp], i });
                V.push_back(contribute[pp]);
            }
            P[pp] = i;
        }
    }
    vector<mint> prod(N+1); prod[0] = 1;
    rep(i,N) prod[i+1] = prod[i] * A[i];
    auto md = nachia::TwoDRectangleQuery<int,int>(points);
    vector<vector<mint>> F(md.getSegmentCount(), vector<mint>(points.size()+1));
    rep(i,F.size()){
        F[i][0] = 1;
        rep(j,points.size()) F[i][j+1] = F[i][j] * V[md.toVtx(i,j)];
    }
    int Q; cin >> Q;
    mint ans = 1;
    //rep(i,points.size()) cout << points[i].first << " " << points[i].second << " " << V[i].val() << endl;
    //cout << endl;
    rep(qi,Q){
        int a,b; cin >> a >> b;
        int l = (ans * mint(a)).val() % N;
        int r = (ans * mint(b)).val() % N;
        if(l > r) swap(l, r);
        r += 1;
        //cout << (l+1) << " " << r << endl;
        mint p = 1;
        mint q = 1;
        rep(i,fairy.size()) if(fairy[i].noLessThan(l) < r) p *= cfairy[i];
        p *= prod[r];
        q *= prod[l];
        for(auto [d,ll,rr] : md.getRanges(l,r,l,r)){
            q *= F[d][rr];
            p *= F[d][ll];
        }
        ans = p / q;
        cout << ans.val() << "\n";
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0