分析

本题的关键是 \(\gcd_{i=1}^n \{a_i\}\) 就是所有出现过的质因数，是所对应的最小次幂之积。

原序列可以看作依次插入。将 \(a_x\) 修改为 \(y\)，本质上是除去所有在 \(a_x\) 分解中的质因数的幂次，然后再将 \(y\) 插入并更新。

所以用std::map来维护某个 \(a_i\) 中所有质因数的幂次，用std::set来维护某个质因数的所有幂次（目的是快速插入，快速查找最小值）。

记录 \(rec_i\) 表示序列中含有质因数 \(i\) 的数字的个数，一旦存在 \(rec_i=n\)，那么答案要累乘 \(i\) 的最小次幂。

具体看代码。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5, mod=1e9+7;
int n, m, cnt, ans=1, p[N], pr[N], rec[N];
map<int,int> mp[N];
multiset<int> st[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void ora() {
	for(int i=2;i<=2e5;++i) {
		if(!p[i]) p[i]=i, pr[++cnt]=i;
        // p[i]表示i的最小质因子
		for(int j=1;j<=cnt&&i*pr[j]<=2e5;++j) {
			p[i*pr[j]]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
}
int fp(int x,int y) {
	x%=mod;	int z=1;
	for(;y;x=x*x%mod,y>>=1) if(y&1) z=z*x%mod;
	return z;
}
int getinv(int x) { return fp(x,mod-2); }
void solve(int x,int y) {
	vector<pair<int,int> > t;
	#define fr first
	#define sc second
	while(y>1) {
		int a=0, d=p[y];
		while(y%d==0) y/=d, ++a;
		t.push_back({d,a});
	}
	for(auto tt:t) {
		int _p=tt.fr, _a=tt.sc;
		if(mp[x][_p]==0) {
            //如果a[x]中没有出现过p这个因子
			++rec[_p], st[_p].insert(_a), mp[x][_p]=_a;
            // 维护
			if(rec[_p]==n) {
				(ans*=fp(_p,*st[_p].begin()))%=mod;
                // 这个因子是所有数的公因子，取最小幂次
			}
		} else {
			if(rec[_p]==n) {
				int inv=getinv(fp(_p,*st[_p].begin()));
				(ans*=inv)%=mod;
                // p已经出现过了，如果p是所有数公因子，就要先让gcd除以p的最小次幂
			}
			st[_p].erase(st[_p].find(mp[x][_p]));
			mp[x][_p]+=_a;
			st[_p].insert(mp[x][_p]);
            // 删除原信息，维护新信息
			if(rec[_p]==n) {
				(ans*=fp(_p,*st[_p].begin()))%=mod;
                // 如果p是公因子，就要更新答案
			}
		}
	}
}
signed main() {
	ora();
	n=read(), m=read();
	for(int i=1;i<=n;++i) {
		int x=read();
		solve(i,x);
	}
	while(m--) {
		int x=read(), y=read();
		solve(x,y);
		printf("%lld\n",ans);
	}
}