本文共 1607 字，大约阅读时间需要 5 分钟。

动态维护每一个质因子的最小值,相乘就是答案.

因为每次只乘上一个数,一个数的质因子最多只有$log(n)$个

所以整体质因子只有$nlog(n)$个,空间复杂度足够

我们可以开一个二维$map$记作$mp[i][j]$表示$a[i]$中有多少质因子$j$

再开一个$multiset$记作$cnt[i]$

$cnt[i]$里面的数是每个$a[i]$拥有的质因子$i$个数,如果质因子是$0$就不插入了

那么如果$cnt[i]$里有$n$个数,说明所有的数都有$i$这个质因子

那么$cnt[i].begin()$就是所有数中最少的$i$的质因子,$i^{cnt[i].begin()}$就是质因子$i$的贡献

所以每次插入$x$,对$x$分解质因子,动态维护$mp[][]$,然后动态维护$cnt$即可

主要是利用了$multiset$平衡树的特性,动态给数值排序第一个数最小

#include 
   
    using namespace std;#define int long longconst int maxn = 3e5+10;const int mod = 1e9+7;map
    
     mp[maxn];multiset
     
      cnt[maxn];int nxt[maxn],n,q,ans=1;void add(int i,int x){
   	while( x!=1 )	{
   		int div = nxt[x], add = 0;		while( nxt[x]==div )	add++, x=x/nxt[x];				int now = mp[i][div];//之前有多少div这个质因子 		mp[i][div] += add;		int mi = 0;//之前所有数的最小质因子数量 		if( cnt[div].size()==n )	mi = (*cnt[div].begin() );		if( now )	cnt[div].erase( cnt[div].find(now) );//抹掉原来的因子 		cnt[div].insert( now+add );//加上现在的因子 		if( cnt[div].size()==n )//计算质因子的贡献 		{
   			int mx = (*cnt[div].begin() );			for(int j=mi+1;j<=mx;j++)	ans = ans*div%mod;		}	}}signed main(){
   	cin >> n >> q;	for(int i=2;i
      
       10000 )	continue;			for(int j=i+i;j
       
        > x, add(i,x);	for(int i=1;i<=q;i++)	{
   		int l,x; cin >> l >> x;		add(l,x);		cout << ans << "\n";	}}
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114483842 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！