原题为2017六省联考的D1T3
给出一个序列，m次操作，模数p和参数c
操作分为两种：
1、将[l,r]区间内的每个数x变为(c^x)
2、求[l,r]区间内数的和%p
首先，我们要了解一些数论姿势：
1、扩展欧拉定理
//我们熟知的费马小定理用于p是质数，欧拉定理用于a,p互质，而这道题都不满足这个限制
当((b>=phi(p)))时，(a^b=a^{bmod phi(p) + phi(p)})
2、（其实不算数论姿势）一个数最多经过log此(phi)就会变成1
所以我们发现，一个数在经过几次变化后，指数永远是(xmod1+1)，也就是1，它就再也不变了！
//上面这里不理解的话，可以考虑这样一道题
//给定一个长度为n的序列a,每次询问区间[l,r] (a_l^{a_{l+1}^{…}})的值。(n<=10^5,m<=10^9)
//原题应该是叫power tower
所以我们建一棵线段树，维护当前区间和和这个区间中被修改的最小次数。
预处理出对于mod p来讲，几次后一定会不变，记为k。每次修改将当前位置的修改次数++。如果这个区间的最小修改次数>=k，那么就不需要修改了，否则暴力修改。
因为每次的修改次数不一样，所以要用初值a[i]计算times后当前数会变为什么。
因为有n个数，每个数会被暴力修改(log(p))次，每次修改是(log(n))的，再乘上快速幂的复杂度(log)就是(O(nlog^3))
这样基本能过了，但是被卡常的话就不稳了。可以考虑预处理c的快速幂，反正c是固定的……
//bzoj不预处理就能过，洛谷过不了（也可能是博主写的比较菜）
贴一份没有预处理的代码
#include<cstdio>
#include<algorithm>
#define N 50010
#define M 10010
typedef long long ll;
using namespace std;
int a[N],n,m,prime[N],tot,p[N],P,c,op,l,r,k,MOD;
bool np[N];
struct hhh
{
int l,r,sum,is;
}tre[4*N];
int read()
{
int ans=0,fu=1;
char j=getchar();
for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;
for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
return ans*fu;
}
int ksm(int x,int y,int mo,bool &flag)
{
int ret=1;
bool big=0;
while (y)
{
if (y&1)
{
flag|=big|((ll)ret*x>=mo);
ret=(ll)ret*x%mo;
}
if ((ll)x*x>=mo) big=1;
x=(ll)x*x%mo;
y>>=1;
}
return ret;
}
void build(int i,int l,int r)
{
tre[i].l=l;tre[i].r=r;tre[i].is=0;
if (l==r)
{
tre[i].sum=a[l]%P;
return ;
}
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
tre[i].sum=(tre[i*2].sum+tre[i*2+1].sum)%P;
}
int calc(int x,int dep)
{
int ret=x;
if (ret>=p[dep]) ret=ret%p[dep]+p[dep];
while (dep)
{
dep--;
bool flag=0;
ret=ksm(c,ret,p[dep],flag);
if (flag) ret+=p[dep];
}
return ret%P;
}
void modify(int i,int l,int r)
{
if (l>tre[i].r || r<tre[i].l) return ;
if (tre[i].is>=k) return ;
if (tre[i].l==tre[i].r)
{
tre[i].is++;
tre[i].sum=calc(a[tre[i].l],tre[i].is);
return ;
}
modify(i*2,l,r);
modify(i*2+1,l,r);
tre[i].sum=(tre[i*2].sum+tre[i*2+1].sum)%P;
tre[i].is=min(tre[i*2].is,tre[i*2+1].is);
}
int query(int i,int l,int r)
{
if (l>tre[i].r || r<tre[i].l) return 0;
if (tre[i].l>=l && tre[i].r<=r) return tre[i].sum;
return (query(i*2,l,r)+query(i*2+1,l,r))%P;
}
int phi(int n)
{
int res=n,a=n;
for(int i=2; i*i<=a; i++)
if(a%i==0)
{
res=res/i*(i-1);
while (a%i==0) a/=i;
}
if (a>1) res=res/a*(a-1);
return res;
}
int main()
{
n=read();m=read();P=read();c=read();
for (int i=1;i<=n;i++) a[i]=read();
p[0]=P;
while (p[k]!=1) { ++k; p[k]=phi(p[k-1]); }
p[++k]=1;
build(1,1,n);
while (m--)
{
op=read();l=read();r=read();
if (op) printf("%d
",query(1,l,r));
else modify(1,l,r);
}
return 0;
}