D. GCD of an Array 数据结构 + 思维

D. GCD of an Array 数据结构 + 思维

题目大意：

给你一个大小为 n 的序列，有 q 次操作，每次操作将 \(a_i\) 乘以 \(x\) ，在每次操作之后输出整个序列的 \(gcd\)

题解：

• 首先明确要对每一个数进行质因数分解，对质数分开讨论
• 然后分解完之后，用map存下来，很简单的想法，就是map存下来之后，然后还要放到一个数据结构里面，通过这个数据结构可以快速的找到最小值，和快速的删去一个值，这个可以用 \(multiset\) ，也可以用两个优先队列（优先队列，一个存值，一个存要删去但是还没有删去的值，如果找到的这个最小值是之前要删去但是没有删去的值，那么直接删掉继续找最小值即可），在这个过程中可以同时求 \(gcd\)
• 最后一步，分析一下复杂度：
  • 首先是一个唯一分解，复杂度是 \(O(n*100)\) 只需要筛1000以内的质数，而1000以内的质数大概是100个左右
  • 然后还有一个add函数的复杂度，注意这个复杂度并不完全依赖于唯一分解，而是可以单独算，和上一步的复杂度相加，这个是因为并不是唯一分解的每一步都会进入这个add 函数，而是在唯一分解过程中，分解出了质数才会进入，所以我只需要算每一个数的质数最多是多少即可。
  • 每一个数的质数最多不会超过10个，所以进入的次数是 \(1e5*10\) ，然后进入之后还是常数个 \(log\) ，所以最后的总复杂度差不多等价于 \(O(n*logn*logn)\)
  • 所以读入+处理的复杂度是 \(O(n*100+n*logn*logn)\)
  • 下面的询问复杂度和读入复杂度一致

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
const int mod = 1e9+7;
const int M = 1e3;
typedef long long ll;
map<int,int>mp[maxn];
multiset<int>st[maxn];
int m,isp[M],v[M];
void init(){
    m = 0;
    for(int i=2;i<M;i++){
        if(v[i]==0) isp[m++] = i,v[i] = i;
        for(int j=0;j<m;j++){
            if(v[i]<isp[j]||i*isp[j]>=M) break;
            v[i*isp[j]] = isp[j];
        }
    }
}
ll gcd;
int n,q;
ll binpow(ll x,ll k) {
    x %= mod;
    ll ans = 1;
    while (k) {
        if (k & 1) ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}
void add(int pos,int p,int num){
//    printf("pos = %d p = %d num = %d\n",pos,p,num);
    if(mp[pos].count(p)){
        if(st[p].size()==n){
            ll tmp = binpow(p,*st[p].begin());
//            printf("!!! tmp = %lld inv = %lld\n",tmp,binpow(tmp,mod-2));
            gcd = gcd * binpow(tmp,mod-2)%mod;
        }
//        printf("!!! gcd = %lld\n",gcd);
        st[p].erase(st[p].find(mp[pos][p]));
        //一定想要用find找到这个迭代器，如果：st[p].erase(x)，则会容器中的所有的x
        mp[pos][p] += num;
        st[p].insert(mp[pos][p]);
        if(st[p].size()==n) gcd = gcd * binpow(p,*st[p].begin())%mod;
//        printf("gcd = %lld\n",gcd);
    }
    else{
        mp[pos][p] = num;
        st[p].insert(mp[pos][p]);
        if(st[p].size()==n) gcd = gcd * binpow(p,*st[p].begin())%mod;
    }
}
void solve(int pos,int x){
    for(int i=0;i<m&&x!=1;i++){
        if(x%isp[i]==0){
            int cur = 0;
            while(x%isp[i]==0) x/=isp[i],cur++;
            add(pos,isp[i],cur);
        }
    }
    if(x!=1) add(pos,x,1);
}
int main(){
    init();
    scanf("%d%d",&n,&q);
    gcd = 1;
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        solve(i,x);
    }
    while(q--){
        int pos,x;
        scanf("%d%d",&pos,&x);
        solve(pos,x);
        printf("%lld\n",gcd);
    }
    return 0;
}