Question
给你一个区间，有修改和查询操作：
修改：将一段区间乘以x
查询：
Solution
我们一看到有欧拉函数，就想到了关于欧拉函数的一些性质：
就是这个性质，我们可以将答案分成两个问来求：
一个是就区间a[i]的乘积，另一个就是包含这个质数的个数。
因为模数是个质数，所以说可以用费马小定理来实现。
这两个都可以用线段树+懒惰标记来实现，而且600以内的质数就只有109个，所以时间复杂度可以保证
Code
#include<cstdio>
#include<cstring>
#define N 10010
#define ll long long
#define mo 100000007
using namespace std;
int prime[610],di[5],cnt=0;
ll t[N*4+10][110],lazy[N*4+10][110];
ll num[N<<3],lz[N<<3],ycl[110];
int n,a[N],q,opt,l,r,X;
bool bz[610],hav[N<<3];
ll ans=0;
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
ll ksm(ll x,int y)
{
ll s=1;
while (y)
{
if (y & 1) s=s*x%mo;
x=x*x%mo,y>>=1;
}
return s;
}
void find(int x)
{
cnt=0;
for (int i=1;i<=109;i++)
if (x%prime[i]==0) di[++cnt]=i;
}
void update(int x,int l,int r)
{
int mid=l+r>>1;
for (int i=1;i<=109;i++)
if (t[x][i]==r-l+1)
t[x<<1][i]=mid-l+1,
t[x<<1|1][i]=r-mid;
hav[x<<1]=hav[x<<1|1]=1;
hav[x]=0;
}
void change(int x)
{
num[x]=num[x<<1]*num[x<<1|1]%mo;
for (int i=1;i<=cnt;i++)
t[x][di[i]]=t[x<<1][di[i]]+t[x<<1|1][di[i]];
}
void build(int x,int l,int r,int f)
{
if (l==r)
{
num[x]=a[f];
for (int i=1;i<=cnt;i++)
t[x][di[i]]=1;
return;
}
int mid=l+r>>1;
if (f<=mid) build(x<<1,l,mid,f);
else build(x<<1|1,mid+1,r,f);
change(x);
}
void plus(int x,int l,int r,int fl,int fr)
{
if (fl<=l && fr>=r)
{
lz[x]=lz[x]*X%mo;
num[x]=num[x]*ksm(X,r-l+1)%mo;
for(int i=1;i<=cnt;i++)
t[x][di[i]]=r-l+1;
hav[x]=1;
return;
}
int mid=l+r>>1;
if (lz[x]>1)
{
num[x<<1]=num[x<<1]*ksm(lz[x],mid-l+1)%mo;
num[x<<1|1]=num[x<<1|1]*ksm(lz[x],r-mid)%mo;
lz[x<<1]=lz[x<<1]*lz[x]%mo;
lz[x<<1|1]=lz[x<<1|1]*lz[x]%mo;
lz[x]=1;
}
if (hav[x]) update(x,l,r);
if (fl<=mid) plus(x<<1,l,mid,fl,fr);
if (fr>mid) plus(x<<1|1,mid+1,r,fl,fr);
change(x);
}
void gans(int x,int l,int r,int fl,int fr)
{
if (fl<=l && fr>=r)
{
ans=ans*num[x]%mo;
for (int i=1;i<=109;i++)
if (t[x][i]>0) ans=ans*ksm(ycl[i],t[x][i])%mo;
return;
}
int mid=l+r>>1;
if (lz[x]>1)
{
num[x<<1]=num[x<<1]*ksm(lz[x],mid-l+1)%mo;
num[x<<1|1]=num[x<<1|1]*ksm(lz[x],r-mid)%mo;
lz[x<<1]=lz[x<<1]*lz[x]%mo;
lz[x<<1|1]=lz[x<<1|1]*lz[x]%mo;
lz[x]=1;
}
if (hav[x]) update(x,l,r);
if (fl<=mid) gans(x<<1,l,mid,fl,fr);
if (fr>mid) gans(x<<1|1,mid+1,r,fl,fr);
}
int main()
{
freopen("runway.in","r",stdin);
// freopen("runway.out","w",stdout);
for (int i=2;i<=600;i++)
if (!bz[i])
{
prime[++prime[0]]=i;
ycl[prime[0]]=(i-1)*ksm(i,mo-2)%mo;
for (int j=1;j<=600/i;j++)
bz[i*j]=1;
}
n=read();
for (int i=1;i<=40000;i++) lz[i]=1;
for (int i=1;i<=n;i++)
a[i]=read(),find(a[i]),build(1,1,n,i);
q=read();
while (q--)
{
opt=read(),l=read(),r=read();
if (opt==0) X=read(),find(X),plus(1,1,n,l,r);
else ans=1,gans(1,1,n,l,r),printf("%lld
",ans);
}
return 0;
}