CF1114F Please, another Queries on Array?
歐拉函數(shù)+線段樹
維護(hù)區(qū)間乘積、區(qū)間質(zhì)因子的或
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
#define int long long
using namespace std;
const int N = 4e5+10,M = 100;
const int mod=1e9+7;
int n,m,prime[N],st[N],cnt,w[N],inv[N];
struct Node{
? ? int l,r;
? ? int v,mul;
? ? bitset<M> p,lzp;
}tr[N*4];
int qmi(int a,int b){
? ? int res=1%mod;
? ? while(b){
? ? ? ? if(b&1) res=res*a%mod;
? ? ? ? a=a*a%mod;
? ? ? ? b>>=1;
? ? }
? ? return res;
}
void init(int n){
? ? for(int i=2;i<=n;i++){
? ? ? ? if(!st[i]) prime[cnt++]=i;
? ? ? ? for(int j=0;i*prime[j]<=n;j++){
? ? ? ? ? ? st[i*prime[j]]=1;
? ? ? ? ? ? if(i%prime[j]==0) break;
? ? ? ? }
? ? }
}
void pushup(Node &u,Node &l,Node &r){
? ? u.v=l.v*r.v%mod;
? ? u.p=l.p|r.p;
}
void pushup(int u){
? ? pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void pushdown(int x){
? ? auto &u=tr[x],&l=tr[x<<1],&r=tr[x<<1|1];
? ? l.v=l.v*qmi(u.mul,l.r-l.l+1)%mod;
? ? r.v=r.v*qmi(u.mul,r.r-r.l+1)%mod;
? ? l.mul=l.mul*u.mul%mod;
? ? r.mul=r.mul*u.mul%mod;
? ? l.p|=u.lzp;
? ? r.p|=u.lzp;
? ? l.lzp|=u.lzp;
? ? r.lzp|=u.lzp;
? ? u.mul=1,u.lzp=0;
}
void build(int u,int l,int r){
? ? if(l==r){
? ? ? ? bitset<M> p;
? ? ? ? for(int i=0;i<cnt;i++)
? ? ? ? ? ? if(w[r]%prime[i]==0)
? ? ? ? ? ? ? ? p[i]=1;
? ? ? ? tr[u]={l,r,w[r],1,p};
? ? ? ? return ;
? ? }
? ? tr[u]={l,r,0,1};
? ? int mid=l+r>>1;
? ? build(u<<1,l,mid),build(u<<1|1,mid+1,r);
? ? pushup(u);
}
void update(int u,int l,int r,int k,int t){
? ? if(tr[u].l>=l&&tr[u].r<=r){
? ? ? ? tr[u].v=tr[u].v*qmi(k,tr[u].r-tr[u].l+1)%mod;
? ? ? ? tr[u].mul=tr[u].mul*k%mod;
? ? ? ? tr[u].p|=t;
? ? ? ? tr[u].lzp|=t;
? ? ? ? return ;
? ? }
? ? pushdown(u);
? ? int mid=tr[u].l+tr[u].r>>1;
? ? if(l<=mid) update(u<<1,l,r,k,t);
? ? if(mid<r) update(u<<1|1,l,r,k,t);
? ? pushup(u);
}
Node query(int u,int l,int r){
? ? if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
? ? pushdown(u);
? ? int mid=tr[u].l+tr[u].r>>1;
? ? if(r<=mid) return query(u<<1,l,r);
? ? else if(l>mid) return query(u<<1|1,l,r);
? ? Node res,a=query(u<<1,l,r),b=query(u<<1|1,l,r);
? ? pushup(res,a,b);
? ? return res;
}
signed main(){
? ? init(300);
? ? for(int i=0;i<cnt;i++)
? ? ? ? inv[i]=(prime[i]-1)*qmi(prime[i],mod-2)%mod;
? ? cin>>n>>m;
? ? for(int i=1;i<=n;i++) cin>>w[i];
? ? build(1,1,n);
? ? while(m--){
? ? ? ? char op[10];
? ? ? ? int l,r,k;
? ? ? ? cin>>op>>l>>r;
? ? ? ? if(op[0]=='M'){
? ? ? ? ? ? int x;
? ? ? ? ? ? cin>>x;
? ? ? ? ? ? int p=0;
? ? ? ? ? ? for(int i=0;i<cnt;i++)
? ? ? ? ? ? ? ? if(x%prime[i]==0)
? ? ? ? ? ? ? ? ? ? p|=(1ll)<<i;
? ? ? ? ? ? update(1,l,r,x,p);
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? Node res=query(1,l,r);
? ? ? ? ? ? int sum=res.v;
? ? ? ? ? ? for(int i=0;i<cnt;i++)
? ? ? ? ? ? ? ? if(res.p[i])
? ? ? ? ? ? ? ? ? ? sum=sum*inv[i]%mod;
? ? ? ? ? ? cout<<sum<<endl;
? ? ? ? }
? ? }
? ??
? ? return 0;
}
