社区讨论

求助,WA了第五个点

CF1114FPlease, another Queries on Array?参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo14l2o1
此快照首次捕获于
2023/10/22 15:06
2 年前
此快照最后确认于
2023/11/02 14:38
2 年前
查看原帖
定义名在代码里有注释
感谢
CPP
#include<iostream>
#define int long long
using namespace std;
const int mod=1e9+7;
int s[75],f[301],cnt;
void xxs()
{
	for(int i=2;i<=300;i++)
	{
		if(!f[i]) s[++cnt]=i;
		for(int j=1;j<=cnt&&s[j]*i<=300;j++)
		{
			f[s[j]*i]=1;
			if(i%s[j]==0) break;
		}
	}
}//线性筛筛300以内质数 
int ksm(int x,int k)
{
	int ans=1;
	while(k)
	{
		if(k&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		k>>=1;
	}
	return ans;
}//快速幂 
int n,q,a[400001],sum[1600001],lazy[1600001],ans,ks[75];//a是给定数组 sum是线段树乘积和 yz是统计出现的质数有哪些 lazy和laz是分别对应两者的lazy_tag ks是已知素数的负一次方(记录了ksm(s[i],mod-2)) 
bool yz[1600001][65],xc[75],laz[1600001][65];
void cal(int id,int x)
{
	for(int i=1;i<=cnt;i++) if(x%s[i]==0&&yz[id][i]==0) yz[id][i]=1;
}
//去统计当前区间有哪些素数已经出现了 
void cal_laz(int id,int x)
{
	for(int i=1;i<=cnt;i++) if(x%s[i]==0&&laz[id][i]==0) laz[id][i]=1;
}
//去统计当前区间有哪些素数已经出现的lazy_tag 
void build(int i,int l,int r)
{
	if(l==r)
	{
		lazy[i]=1;
		sum[i]=a[l];
		cal(i,a[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	sum[i]=(sum[i<<1]*sum[i<<1|1])%mod;
	lazy[i]=1;
	for(int j=1;j<=cnt;j++) if(yz[i<<1][j]==1||yz[i<<1|1][j]==1) yz[i][j]=1;
}
//建树 
void mul(int i,int l,int r,int l1,int r1,int x)
{
	if(l>r1||r<l1) return ;
	if(l1<=l&&r<=r1)
	{
		lazy[i]=(lazy[i]*x)%mod;
		cal_laz(i,x);
		return ;
	}
	int mid=(l+r)>>1;
	mul(i<<1,l,mid,l1,r1,x);
	mul(i<<1|1,mid+1,r,l1,r1,x);
}
//区间乘 
void upd(int i,int l,int r)
{
	lazy[i<<1]=(lazy[i<<1]*lazy[i])%mod;
	lazy[i<<1|1]=(lazy[i<<1|1]*lazy[i])%mod;
	for(int j=1;j<=cnt;j++) if(laz[i<<1][j]==0&&laz[i][j]==1) laz[i<<1][j]=1;
	for(int j=1;j<=cnt;j++) if(laz[i<<1|1][j]==0&&laz[i][j]==1) laz[i<<1|1][j]=1;
	sum[i]=(sum[i]*ksm(lazy[i],r-l+1));
	lazy[i]=1;
	for(int j=1;j<=cnt;j++)
	{
		if(yz[i][j]==0&&laz[i][j]==1) yz[i][j]=1;
		laz[i][j]=0;
	}
}
//update 
void que(int i,int l,int r,int l1,int r1)
{
	if(l>r1||r<l1) return ;
	upd(i,l,r);
//	cout<<i<<" "<<l<<" "<<r<<" "<<sum[i]<<endl;
//	for(int j=1;j<=3;j++) cout<<yz[i][j]<<" ";
//	cout<<endl;
	if(l1<=l&&r<=r1)
	{
		ans=(ans*sum[i])%mod;
		for(int j=1;j<=cnt;j++)
		{
			if(yz[i][j]) 
			{
				ans=(ans*ks[j])%mod;
				ans=(ans*(s[j]-1))%mod;
			}
		}
		return ;
	}
	int mid=(l+r)>>1;
	que(i<<1,l,mid,l1,r1);
	que(i<<1|1,mid+1,r,l1,r1);
}
signed main()
{
	xxs();
	for(int i=1;i<=cnt;i++) ks[i]=ksm(s[i],mod-2);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int ll=1;ll<=q;ll++)
	{
		string s;
		int lll,rr,xx;
		cin>>s;
		if(s=="MULTIPLY")
		{
			cin>>lll>>rr>>xx;
			mul(1,1,n,lll,rr,xx);
		}else
		{
			ans=1;
			cin>>lll>>rr;
			que(1,1,n,lll,rr);
			cout<<ans<<endl; 
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...