题目传送门

这道题有一个非常牛逼的数据结构就是 m u l t i s e t multiset multiset

题意

先给你一个序列，然后给你几组询问，询问的第一个数是在第x个位置上，第二个数p代表，在第x个位置上乘p。请找到这个序列的gcd，并输出。

思路

这道题肯定是让你找到所有数的公共的因子，那么就可以以因子为下标，存到 m u l t i s e t multiset multiset里面，同时开一个数组标记一下，这个数作为了几个数的因子。如果能找到这个因子，并这个数已经作为全部的因子，答案乘这个数。

#include<iostream>
#include<set>
#define huzanjujutaiqiangle signed main()
//#define int long long 
#define MAXN 250005
//#define MOD 1e9+7
using namespace std;
typedef long long ll;
multiset<int>s[MAXN];
const ll MOD=1e9+7;
int p[MAXN<<1];
bool st[MAXN<<1];
int primes[MAXN<<1];
int cnt;
ll gcd=1;
int _hash[MAXN<<1];
int n,m;

void get_minmu(){
	p[1]=1;
	for(int i=2;i<=500000;i++){
		/*if(i==500000){
			cout<<"ok"<<endl;
		}*/
		//cout<<i<<endl;
		if(!st[i]){
			p[i]=i;
			primes[++cnt]=i;	
		}
		for(int j=1;j<=cnt&&i*primes[j]<=MAXN;j++){
			st[primes[j]*i]=true;
			p[primes[j]*i]=primes[j];
			if(i%primes[j]==0)break;
		}
	}
	
}
int modify(int x,int t){
	while(t!=1){
		if(s[p[t]].find(x)==s[p[t]].end()){
			++_hash[p[t]];
		}
		s[p[t]].insert(x);
		if(_hash[p[t]]==n){
			gcd*=(ll)p[t];
			gcd%=MOD;
			_hash[p[t]]=0;
			for(int i=1;i<=n;i++){
				s[p[t]].erase(s[p[t]].find(i));
				if(s[p[t]].find(i)!=s[p[t]].end()){
					++_hash[p[t]];
				}
			}
		}
		t/=p[t];
	}
}
huzanjujutaiqiangle{
	get_minmu();
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		//int t;
		//cin>>t;
		modify(i,t);
	}
	while(m--){
		int x,t;
		scanf("%d %d",&x,&t);
		//cin>>x>>t;
		modify(x,t);
		printf("%lld\n",gcd);
		//cout<<gcd<<endl;
	}
	//cout<<gcd<<endl;
}