社区讨论
求助,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 条回复,欢迎继续交流。
正在加载回复...