CF1493D GCD of an Array（动态开点线段树）

经典套路

动态开点维护质数个线段树，这样我们每次在质数上插入，只要维护一个最小值查询就能知道对于这个质数的最小的那个是谁

因为一个数分解的质数不会太多，主要是数不大，所以做法合理

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pll;
const int N=3e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct node{
    int l,r;
    int mi;
}tr[N<<2];
int idx,primes[N],cnt,st[N];
int rk[N],rt[N];
void init(){
    int i;
    for(i=2;i<=200000;i++){
        if(!st[i]){
            primes[++cnt]=i;
        }
        for(int j=1;primes[j]*i<=200000;j++){
            st[primes[j]*i]=1;
            if(i%primes[j]==0)
                break;
        }
    }
    for(i=2;i<=200000;i++){
        st[i]=!st[i];
        rk[i]=rk[i-1]+st[i];
    }
}
void pushup(int u){
    tr[u].mi=min(tr[tr[u].l].mi,tr[tr[u].r].mi);
}
void modify(int &u,int l,int r,int x,int k){
    if(!u) u=++idx;
    if(l==r){
        tr[u].mi+=k;
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid)
        modify(tr[u].l,l,mid,x,k);
    else
        modify(tr[u].r,mid+1,r,x,k);
    pushup(u);
}
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    init();
    int n,m;
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++){
        int x;
        cin>>x;
        for(j=1;j<=cnt;j++){
            int d=0;
            if(primes[j]*primes[j]>x)
                break;
            while(x%primes[j]==0){
                d++;
                x/=primes[j];
            }
            if(d)
                modify(rt[rk[primes[j]]],1,n,i,d);
            if(x<=1)
                break;
        }
        if(st[x]){
            modify(rt[rk[x]],1,n,i,1);
        }
    }
    ll ans=1;
    for(i=1;i<=cnt;i++){
        ans=ans*qmi(primes[i],tr[rt[rk[primes[i]]]].mi)%mod;
    }
    while(m--){
        int h,x;
        cin>>h>>x;
        for(i=1;i<=cnt;i++){
            int d=0;
            if(primes[i]*primes[i]>x)
                break;
            while(x%primes[i]==0){
                x/=primes[i];
                d++;
            }
            if(d){
                ll last=tr[rt[rk[primes[i]]]].mi;
                modify(rt[rk[primes[i]]],1,n,h,d);
                ll tmp=tr[rt[rk[primes[i]]]].mi;
                ans=ans*qmi(primes[i],(tmp-last))%mod;
            }
            if(x<=1)
                break;
        }
        if(st[x]){
            ll last=tr[rt[rk[x]]].mi;
            modify(rt[rk[x]],1,n,h,1);
            ll tmp=tr[rt[rk[x]]].mi;
            ans=ans*qmi(x,(tmp-last))%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}