CodeForces - 1422F Boring Queries（区间LCM）

传送门：CodeForces - 1422F

思路分析

因为值域很小，所以我们可以维护素因子，考虑素因子对LCM的贡献，小于500的素因子开86个ST表维护区间最大值，大于500的素因子维护去重后区间乘积（主席树）

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 1e5+5;
const int mod = 1e9+7;

#define int long long
int a[N],n;
int prim[99],pcnt;

struct node1 {
    short MAX[N][18];

    void init() {
        for(int j = 1; j<=17; j++) {
            for(int i=1; i+(1<<j)-1<=n; i++) {
                MAX[i][j] = max(MAX[i][j-1],MAX[i+(1<<(j-1))][j-1]);
            }
        }
    }

    int query(int l,int r) {
        int k = log2(r-l+1);
        return max(MAX[l][k],MAX[r-(1<<k)+1][k]);
    }
} ST[87];


bool isp[500];

ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return res;
}

void init() {
    for(int i=2; i*i<200000; i++) {
        if(!isp[i]) {
            prim[++pcnt] = i;
            for(int j = 2*i; j*j<200000; j+=i) isp[j] = true;
        }
    }
}

struct node {
    int l,r,sum;
    node() {
        sum = 1;
    }
} tree[N*40];

int root[N],last[N*2],cnt;

#define ls(x) tree[x].l
#define rs(x) tree[x].r

void pp(int x) {
    tree[x].sum = tree[ls(x)].sum * tree[rs(x)].sum%mod;
}

void ins(int &x,int pre,int l,int r,int pos,int k) {
    tree[++cnt] = tree[pre];
    x = cnt;
    if(l==r) {
        tree[x].sum = k;
        return ;
    }
    int mid = l+r>>1;
    if(pos<=mid) ins(ls(x),ls(pre),l,mid,pos,k);
    else ins(rs(x),rs(pre),mid+1,r,pos,k);
    pp(x);
}


int query(int x,int l,int r,int L,int R) {
    if(L<=l && r<=R) return tree[x].sum;
    int ans = 1;
    int mid = l+r>>1;
    if(L<=mid) ans = (ans*query(ls(x),l,mid,L,R))%mod;
    if(R>mid) ans = (ans*query(rs(x),mid+1,r,L,R))%mod;
    return ans;
}


signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    read(n);
    init();
    for(int i=1; i<=n; i++) {
        read(a[i]);
        for(int j = 1; j<=pcnt && prim[j]<=a[i]; j++) {
            while(a[i]%prim[j] == 0) ST[j].MAX[i][0]++,a[i]/=prim[j];
        }
        root[i] = root[i-1];
        if(a[i] == 1) continue;
        if(last[a[i]]) {
            ins(root[i],root[i-1],1,n,last[a[i]],1);
            ins(root[i],root[i],1,n,i,a[i]);
        }else{
            ins(root[i],root[i-1],1,n,i,a[i]);
        }
        last[a[i]] = i;
    }
    for(int i=1; i<=86; i++) ST[i].init();
    int LAST = 0;
    int m;
    read(m);
    while(m--) {
        int l,r;
        read(l,r);
        l = (l+LAST)%n+1;
        r = (r+LAST)%n+1;
        if(l>r) swap(l,r);
        int ans = query(root[r],1,n,l,r);
        for(int i=1; i<=86; i++) {
            ans = (ans * qpow(prim[i],ST[i].query(l,r)))%mod;
        }
        printf("%lld\n",LAST = ans);
    }


    return 0;
}