Codeforces 1493D（数学+数据结构）

题目描述

给定\(n\)个数和\(q\)个询问，每次询问给出两个数\(i\)和\(x\)，表示将数组中的第\(i\)个数乘上\(x\)，每次询问过后，求\(gcd(a_{1},a_{2},...,a_{n})\)。答案可能会很大，注意结果对\(10^{9}+7\)取模。

思路

考虑对每个数进行质因数分解，答案显然为\(\prod_{i=1}^{n}{p^{min(c_{i})}}\)。
由于每次乘上的值都是小于等于\(2*10^{5}\)，所以我们可以打一个范围内的素数表，然后再对每个数分解质因数。
现在的问题变成了如何维护对应质因数指数的最小值，可以使用STL中的\(multiset\)来保存每个质数的指数，使用\(map\)来保存每个位置对应的数分解后的质数的指数。由于\(multiset\)中的元素是有序的，所以可以在\(O(logn)\)的时间内查到指数最小值。
如果对于每次询问都遍历一遍数组求\(gcd\)，则复杂度为\(O(nq+size(primes)qlogn)\),是肯定会超时的。由于每次都会乘上一个值，所以\(gcd\)在\(q\)个询问的过程中，要么不变，要么增加，所以我们可以对于每次询问，不用重新遍历，而是再之前的基础上进行改变即可，时间复杂度为\(O(size(primes)qlogn)\)。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"

using namespace std;

#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(ll x=l;x=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1) 

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;


struct Scanner {
 
    bool hasNext = 1;
    bool hasRead = 1;
 
    int nextInt() {
        hasRead = 0;
        int res = 0;
        char flag = 1, ch = getchar();
        while(ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while(ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return res * flag;
    }
 
    ll nextLL() {
        hasRead = 0;
        ll res = 0;
        char flag = 1, ch = getchar();
        while(ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while(ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return res * flag;
    }
 
    char nextChar() {
        hasRead = 0;
        char ch = getchar();
        while(ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return ch;
    }
 
    int nextString(char *str) {
        hasRead = 0;
        int len = 0;
        char ch = getchar();
        while(ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        while(ch != EOF && !isspace(ch)) {
            hasRead = 1;
            str[++len] = ch;
            ch = getchar();
        }
        str[len + 1] = 0;
        if(ch == EOF)
            hasNext = 0;
        return len;
    }
 
} sc;
 
ll rd() {
    ll x = sc.nextLL();
    return x;
}
 
void rd(int &x) {
    x = sc.nextInt();
}
 
void rd(ll &x) {
    x = sc.nextLL();
}
 
void rd(char &x) {
    x = sc.nextChar();
}
 
void rd(char* x) {
    sc.nextString(x);
}
 
template
void rd(pair &x) {
    rd(x.first);
    rd(x.second);
}
 
template
void rd(T *x, int n) {
    for(int i = 1; i <= n; ++i)
        rd(x[i]);
}

template
void rd(vector &x,int n){
    for(int i = 1; i <= n; ++i)
        rd(x[i]);
}
 
void printInt(int x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
        printInt(x / 10);
    putchar('0' + x % 10);
}
 
void printLL(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
        printLL(x / 10);
    putchar('0' + x % 10);
}
 
void pr(int x, char ch = '\n') {
    printInt(x);
    putchar(ch);
}
 
void pr(ll x, char ch = '\n') {
    printLL(x);
    putchar(ch);
}

//#define LOCAL
template
void pr(pair x, char ch = '\n') {
#ifdef LOCAL
    putchar('<');   
    pr(x.first, ' ');
    pr(x.second, '>');
    putchar(ch);
    return;
#endif //LOCAL
    pr(x.first, ' ');
    pr(x.second, ch);
}
template
void pr(T *x, int n) {
    for(int i = 1; i <= n; ++i)
        pr(x[i], " \n"[i == n]);
}
 
template
void pr(vector &x) {
    int n = x.size();
    for(int i = 1; i <= n - 1; ++i)
        pr(x[i], " \n"[i == n - 1]);
}

const int N=2*1e5+5;
const int M=1<<12;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);

vector primes;
bool v[N];
map mp[N];
multiset cnt[N];
int n,q;
ll ans=1;
void get_prime(){
    rep(i,2,N){
        if(!v[i]){
            primes.PB(i);
        }
        for(int j=0;primes[j]<=N/i;j++){
            v[primes[j]*i*1ll]=true;
            if(i%primes[j]==0) break;
        }
    }
}
void add(int pos,int val){
    rep(i,0,sz(primes)){
        if(primes[i]*1ll*primes[i]>val) break;
        if(val%primes[i]==0){
            int cnt1=0;
            while(val%primes[i]==0){
                val/=primes[i];
                cnt1++;
            }
            int last=mp[pos][primes[i]];
            mp[pos][primes[i]]+=cnt1;
            int mn=0;
            if(sz(cnt[primes[i]])==n) mn=*cnt[primes[i]].begin();
            if(last) cnt[primes[i]].erase(cnt[primes[i]].find(last));
            cnt[primes[i]].insert(last+cnt1);
            if(sz(cnt[primes[i]])==n){
                int now=*cnt[primes[i]].begin();
                rep(j,mn,now) ans=(ans*1ll%mod*primes[i]+mod)%mod;
            }
        }
    }
    if(val>1){
        int last=mp[pos][val];
        mp[pos][val]++;
        int mn=0;
        if(sz(cnt[val])==n) mn=*cnt[val].begin();
        if(last) cnt[val].erase(cnt[val].find(last));
        cnt[val].insert(last+1);
        if(sz(cnt[val])==n){
            int now=*cnt[val].begin();
            rep(j,mn,now) ans=ans*1ll%mod*val%mod;
        }
    }
}
void solve(){
    rd(n);rd(q);
    rep(i,1,n+1){
        int x;rd(x);
        add(i,x);
    } 
    rep(i,1,q+1){
        int a,x;
        rd(a);rd(x);
        add(a,x);
        pr(ans%mod);
    }
}
int main(){
    //IOS;
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    get_prime();
    //int t;rd(t);
    //rep(i,0,t){
        //printf("Case #%d: ", i+1);
        solve();
    //}
    return 0;
}