就是让你求这个：
传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=5394
解题思路：
NOIP2018后第一道题，感觉非常像那个上帝与集合的正确用法。
具体来说就是使用递归的求解方式，不过这次和上帝与集合的正确用法不同的是：
1.这次不是无限项，所以可以不在p=0时停止。
2.因为被取模数有限大，所以要特判小于φ(p)的情况。
3.询问时要预先处理φ(p)
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll spc<<1
#define rrr spc<<1|1
#define maxval 20000000
typedef long long lnt;
struct trnt{
lnt val;
lnt lzt;
}tr[];
int prime[];
int eula[];
bool vis[];
int cnt;
int n,m;
lnt a[];
lnt read(void)
{
lnt ans=;
lnt f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch<=''&&ch>='')
{
ans=ans*10ll+(lnt)(ch-'');
ch=getchar();
}
return ans*f;
}
void Get_prime(void)
{
for(int i=;i<=maxval;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
eula[i]=i-;
}
vis[i]=false;
for(int j=;j<=cnt&&(i*prime[j]<=maxval);j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==)
{
eula[i*prime[j]]=eula[i]*prime[j];
break;
}
eula[i*prime[j]]=eula[i]*(prime[j]-);
}
}
return ;
}
void Add(int spc,int l,int r,lnt v)
{
tr[spc].val+=v*(lnt)(r-l+);
tr[spc].lzt+=v;
return ;
}
void pushup(int spc)
{
tr[spc].val=tr[lll].val+tr[rrr].val;
return ;
}
void pushdown(int spc,int l,int r)
{
if(tr[spc].lzt)
{
int mid=(l+r)>>;
Add(lll,l,mid,tr[spc].lzt);
Add(rrr,mid+,r,tr[spc].lzt);
tr[spc].lzt=;
}
return ;
}
void build(int l,int r,int spc)
{
if(l==r)
{
tr[spc].val=a[l];
return ;
}
int mid=(l+r)>>;
build(l,mid,lll);
build(mid+,r,rrr);
pushup(spc);
return ;
}
void update(int l,int r,int ll,int rr,int spc,lnt v)
{
if(ll>r||l>rr)
return ;
if(ll<=l&&r<=rr)
{
Add(spc,l,r,v);
return ;
}
int mid=(l+r)>>;
pushdown(spc,l,r);
update(l,mid,ll,rr,lll,v);
update(mid+,r,ll,rr,rrr,v);
pushup(spc);
return ;
}
lnt query(int l,int r,int spc,int pos)
{
if(l==r)
return tr[spc].val;
int mid=(l+r)>>;
pushdown(spc,l,r);
if(pos<=mid)
return query(l,mid,lll,pos);
return query(mid+,r,rrr,pos);
}
lnt ksm(lnt a,lnt b,lnt mod,int plc)
{
lnt ans=;
while(b)
{
if(b&)
{
ans=ans*a;
if(ans>=mod)
{
ans%=mod;
vis[plc]=true;
}
}
a=a*a;
if(a>=mod)
{
a%=mod;
vis[plc]=true;
}
b/=;
}
return ans;
}
lnt Query(int l,int r,int p)
{
vis[l]=false;
lnt tmp=query(,n,,l);
if(tmp>=p)
vis[l]=true;
tmp%=p;
if(tmp==)
return ;
if(p==)
return ;
if(l==r)
return tmp%p;
lnt temp=eula[p];
return ksm(tmp,Query(l+,r,temp)+vis[l+]*temp,p,l);
}
int main()
{
Get_prime();
n=read();
m=read();
for(int i=;i<=n;i++)
a[i]=read();
build(,n,);
while(m--)
{
lnt cmd=read(),l=read(),r=read(),x=read();
if(cmd==)
update(,n,l,r,,x);
else
printf("%lld\n",Query(l,r,x));
}
return ;
}