| 123456789 |
- #include <array>
- #include <cstdint>
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;constexpr long long MOD=1000000007;
- long long power(long long a,long long b){long long r=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)r=r*a%MOD;return r;}
- struct Node{long long product=1,lazy_mul=1;uint64_t mask=0,lazy_mask=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);vector<int>primes;for(int x=2;x<=300;++x){bool ok=true;for(int p=2;p*p<=x;++p)if(x%p==0)ok=false;if(ok)primes.push_back(x);}array<uint64_t,301>factor{};for(int x=1;x<=300;++x)for(int i=0;i<(int)primes.size();++i)if(x%primes[i]==0)factor[x]|=uint64_t(1)<<i;int n,q;cin>>n>>q;vector<int>a(n);for(int&x:a)cin>>x;vector<Node>tr(4*n);auto pull=[&](int u){tr[u].product=tr[u*2].product*tr[u*2+1].product%MOD;tr[u].mask=tr[u*2].mask|tr[u*2+1].mask;};auto apply=[&](int u,int l,int r,long long x,uint64_t mask){tr[u].product=tr[u].product*power(x,r-l+1)%MOD;tr[u].mask|=mask;tr[u].lazy_mul=tr[u].lazy_mul*x%MOD;tr[u].lazy_mask|=mask;};auto push=[&](int u,int l,int r){if(l==r)return;int m=(l+r)/2;if(tr[u].lazy_mul!=1||tr[u].lazy_mask){apply(u*2,l,m,tr[u].lazy_mul,tr[u].lazy_mask);apply(u*2+1,m+1,r,tr[u].lazy_mul,tr[u].lazy_mask);tr[u].lazy_mul=1;tr[u].lazy_mask=0;}};auto build=[&](auto&&self,int u,int l,int r)->void{if(l==r){tr[u].product=a[l];tr[u].mask=factor[a[l]];return;}int m=(l+r)/2;self(self,u*2,l,m);self(self,u*2+1,m+1,r);pull(u);};auto update=[&](auto&&self,int u,int l,int r,int ql,int qr,int x)->void{if(qr<l||r<ql)return;if(ql<=l&&r<=qr){apply(u,l,r,x,factor[x]);return;}push(u,l,r);int m=(l+r)/2;self(self,u*2,l,m,ql,qr,x);self(self,u*2+1,m+1,r,ql,qr,x);pull(u);};auto ask=[&](auto&&self,int u,int l,int r,int ql,int qr)->pair<long long,uint64_t>{if(ql<=l&&r<=qr)return{tr[u].product,tr[u].mask};push(u,l,r);int m=(l+r)/2;pair<long long,uint64_t>z={1,0};if(ql<=m){auto x=self(self,u*2,l,m,ql,qr);z.first=z.first*x.first%MOD;z.second|=x.second;}if(qr>m){auto x=self(self,u*2+1,m+1,r,ql,qr);z.first=z.first*x.first%MOD;z.second|=x.second;}return z;};build(build,1,0,n-1);while(q--){string op;int l,r;cin>>op>>l>>r;--l;--r;if(op[0]=='M'){int x;cin>>x;update(update,1,0,n-1,l,r,x);}else{auto [ans,mask]=ask(ask,1,0,n-1,l,r);for(int i=0;i<(int)primes.size();++i)if(mask>>i&1)ans=ans*(primes[i]-1)%MOD*power(primes[i],MOD-2)%MOD;cout<<ans<<'\n';}}}
|
