4869: [Shoi2017]相逢是问候
先说点正经的……
显然做了有限次（我只知道是有限次，而且不会大，别人说是log次？）修改以后会达到不动点，即以后怎么修改都不变了。
然后就随便做了。（3个log不知道是不是暴力啊）
但是需要拓展欧拉定理：
p与a不互质时，设c=b mod φ(p)（专门设出来是因为公式不能正常显示），如果b>=φ(p)：$a^b ≡ a^{c+φ(p)}$（注意b<φ(p)的时候不能用）
要证明的话可以用数学归纳法证。
可是题目翻车了……
大家都质疑题目数据有问题
得知这一点，窝的瓜心是崩溃的。
这可是省选题，关系到六个省的oier的命运。
我认识的几位dalao就参加了这场省选，有的进队，有的从此AFO。
过几天我也要省选了，要是出了类似的差错被卡退役，西瓜可是不会同意的。
为退役的选手们惋惜，也只能祝他们高考加油了。
（也许过几天就轮到我了呢？
瓜之将死，其言也善
upd:后来bzoj上数据更正了呢
#include<cstdio>
#include<algorithm>
#define MN 100001
#define lp p<<1
#define rp (p<<1)|1
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
int n,m,MOD,c,w=,S[MN],W[MN],a[MN],P[MN],num=,t,l,r,sum[MN<<];
bool bo[MN<<],bi[MN];
inline void M(int &x){while(x>=MOD)x-=MOD;}
inline int mi(int x,int y,int MOD,bool &bi){
int mmh=;
bool fx=;
while (y){
if (y&) bi|=fx|(1LL*x*mmh>=MOD),mmh=1LL*mmh*x%MOD;
fx|=1LL*x*x>=MOD;x=1LL*x*x%MOD;y>>=;
}
return mmh;
}
inline int phi(int p){
int o=;
for (int i=;P[i]*P[i]<=p&&i<=num;i++)
if (p%P[i]==){
p/=P[i];o*=P[i]-;
while (p%P[i]==) p/=P[i],o*=P[i];
}
if (p-) o*=p-;
return o;
}
void work(int p){
S[w++]=p;
if (p==) return;
work(phi(p));
}
int Mavis(int a,int L){
int mmh=a%S[L];
bool bi=a>=S[L];
for (int k=L;k;k--) mmh=mi(c,mmh+(bi?S[k]:),S[k-],bi);
return mmh;
}
void cg(int p,int l,int r,int L,int R){
if (bo[p]) return;
if (l==r) {W[l]++;bo[p]=(W[l]==w-);sum[p]=Mavis(a[l],W[l]);return;}
int mid=l+r>>;
if (R<=mid) cg(lp,l,mid,L,R);else
if (L>mid) cg(rp,mid+,r,L,R);else
cg(lp,l,mid,L,mid),cg(rp,mid+,r,mid+,R);
bo[p]=bo[lp]&bo[rp];
M(sum[p]=sum[lp]+sum[rp]);
}
void build(int p,int l,int r){
bo[p]=;
if (l==r) sum[p]=a[l];else{
int mid=l+r>>;
build(lp,l,mid);build(rp,mid+,r);
M(sum[p]=sum[lp]+sum[rp]);
}
}
int ask(int p,int l,int r,int L,int R){
if (l>=L&&r<=R) return sum[p];
if (l>R||r<L) return ;
int mid=l+r>>;
return (ask(lp,l,mid,L,R)+ask(rp,mid+,r,L,R))%MOD;
}
int main(){
register int i,j,k;
n=read();m=read();MOD=read();c=read();
for (i=;i*i<=MOD;i++){
if (!bo[i]) P[++num]=i;
for (j=;j<=num&&i*P[j]*i*P[j]<=MOD;j++) if (bo[i*P[j]]=,i%P[j]==) break;
}
work(MOD);S[w++]=;
for (i=;i<=n;i++) a[i]=read(),W[i]=;
build(,,n);
while (m--) if (t=read(),l=read(),r=read(),t==) cg(,,n,l,r);else printf("%d\n",ask(,,n,l,r));
}
upd:后来我退役了呢