题目
给一个长度为(n)的数组(a)，(q)次询问
支持区间乘(x)以及求(varphi(prod_{i=l}^ra_i))
(nleq 4*10^5,qleq 2*10^5,xleq 300)
分析
之前我做过一道这个题目
方法就是建109棵线段树维护每个位置是否能被某个质数整除，以及一个维护区间乘的线段树
然后我把这道题改一改交到本题上结果发现MLE了，我还没发现这两题的区别，对于之前的这道题，还要记录每个位置质数的个数
但是对于这道题，实际上只需要维护一个二进制状态表示质因数分解的情况，然后取出这个二进制状态计算欧拉函数
时间复杂度(O(qlogn))
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long lll; const int N=400011,mod=1000000007; int n,m,a[N],inv[N];
const int prime[62]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed ksm(int x,int y){
rr int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
struct rec{
lll w1,w2;
rec operator *(const rec &t)const{
return (rec){w1*t.w1%mod,w2|t.w2};
}
};
struct segt{
lll lazy[N<<2],Lazy[N<<2]; rec w[N<<2];
inline void build(int k,int l,int r){
lazy[k]=1,Lazy[k]=0;
if (l==r){
w[k].w1=a[l];
for (rr int i=0;i<62;++i)
if (a[l]%prime[i]==0)
w[k].w2|=1ll<<i;
return;
}
rr int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
w[k]=w[k<<1]*w[k<<1|1];
}
inline void spread(int k,int len,int z,lll Z){
lazy[k]=lazy[k]*z%mod,Lazy[k]|=Z;
w[k]=(rec){w[k].w1*ksm(z,len)%mod,w[k].w2|=Z};
}
inline void pushdown(int k,int l,int r,int mid){
if (!Lazy[k]) return;
rr int len1=mid-l+1,len2=r-mid;
spread(k<<1,len1,lazy[k],Lazy[k]);
spread(k<<1|1,len2,lazy[k],Lazy[k]);
lazy[k]=1,Lazy[k]=0;
}
inline rec query(int k,int l,int r,int x,int y){
if (l==x&&r==y) return w[k];
rr int mid=(l+r)>>1; pushdown(k,l,r,mid);
if (y<=mid) return query(k<<1,l,mid,x,y);
else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
else return query(k<<1,l,mid,x,mid)*query(k<<1|1,mid+1,r,mid+1,y);
}
inline void update(int k,int l,int r,int x,int y,int z,lll Z){
if (l==x&&r==y){
spread(k,r-l+1,z,Z);
return;
}
rr int mid=(l+r)>>1; pushdown(k,l,r,mid);
if (y<=mid) update(k<<1,l,mid,x,y,z,Z);
else if (x>mid) update(k<<1|1,mid+1,r,x,y,z,Z);
else update(k<<1,l,mid,x,mid,z,Z),update(k<<1|1,mid+1,r,mid+1,y,z,Z);
w[k]=w[k<<1]*w[k<<1|1];
}
}tre;
signed main(){
n=iut(),m=iut();
for (rr int i=0;i<62;++i) inv[i]=1ll*(prime[i]-1)*ksm(prime[i],mod-2)%mod;
for (rr int i=1;i<=n;++i) a[i]=iut();
tre.build(1,1,n);
for (rr char c;m;--m){
c=getchar();
while (c!='T'&&c!='M') c=getchar();
rr int l=iut(),r=iut();
if (c=='T'){
rr rec ANS=tre.query(1,1,n,l,r);
for (rr int i=0;i<62;++i)
if ((ANS.w2>>i)&1){
ANS.w1=1ll*ANS.w1*inv[i]%mod;
}
print(ANS.w1),putchar(10);
}
else{
rr int x=iut(); rr lll T=0;
if (x==1) continue;
for (rr int i=0;i<62;++i)
if (x%prime[i]==0) T|=1ll<<i;
tre.update(1,1,n,l,r,x,T);
}
}
return 0;
}