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

考虑对每个质因子维护一颗动态开点线段树

质因子$v$的线段树的下标是$[1,n]$,表示第$i$个数有多少质因子$v$

因为只有$q$次操作,每次乘以$x$,我们对$x$质因子分解

由于$x$只有$log(x)$个质因子,所以我们可以暴力对每种质因子的线段树修改

总共修改次数是$qlog(x)$,单词修改复杂度是$log(n)$

整体复杂度$qlog(x)log(n)$(比较粗略的计算)

比官方题解快一倍

#include 
   
    using namespace std;const int mod = 1e9+7;const int maxn = 3e5+10;int quick(int x,int n){
   	int ans = 1;	for( ; n ; n>>=1,x=1ll*x*x%mod )		if( n&1 )	ans = 1ll*ans*x%mod;	return ans;}int prime[maxn],vis[maxn],top,n,q;vector
    
     fac[maxn];void make_prime(){
   	for(int i=2;i<=200000;i++)	{
   		if( !vis[i] )	prime[++top] = i;		for(int j=1;j<=top&&prime[j]*i<=200000;j++)		{
   			vis[i*prime[j]] = 1;			if( i%prime[j]==0 )	break;		}	}	for(int i=1;i<=top;i++)	for(int j=prime[i];j<=200000;j+=prime[i] )		fac[j].push_back( prime[i] );}int ls[maxn<<6],rs[maxn<<6],root[maxn<<1],mi[maxn<<6],num;void update(int &rt,int l,int r,int id,int val){
   	if( l>id||r
     
      >1;	update( ls[rt],l,mid,id,val); update( rs[rt],mid+1,r,id,val);	mi[rt] = min( mi[ls[rt]],mi[rs[rt]] );}signed main(){
   	make_prime();	cin >> n >> q;	for(int i=1;i<=n;i++)	{
   		int x,sum; scanf("%d",&x); sum = x;		for( auto v:fac[x] )		{
   			int now = 0;			while( sum%v==0 )	sum/=v,now++;			if( now )	update( root[v],1,n,i,now );		}	}	int ans = 1;	for(int i=1;i<=top;i++)	ans = ans*quick( prime[i],mi[root[prime[i]]] )%mod;	while( q-- )	{
   		int id,x,sum; scanf("%d%d",&id,&x); sum = x;		for( auto v:fac[x] )		{
   			int now = 0;			while( sum%v==0 )	sum/=v,now++;			if( now==0 )	continue;			ans = 1ll*ans*quick( quick( v,mi[root[v]] ),mod-2 )%mod;			update( root[v],1,n,id,now );						ans = 1ll*ans*quick( v,mi[root[v]] )%mod;		}		printf("%d\n",ans); 	}}
     
    
   

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