BZOJ 5394 [Ynoi2016]炸脖龙 (线段树+拓展欧拉定理)

题目大意:给你一个序列,需要支持区间修改,以及查询一段区间$a_{i}^{a_{i+1}^{a_{i+2}...}}mod\;p$的值,每次询问的$p$的值不同

对于区间修改,由线段树完成,没什么好说的

对于查询,利用"上帝与集合的正确用法"那道题的方法,不断取$\phi(p)$降幂,那么最多迭代$log$层

由于$ai$不一定和$p$互质,需要使用拓展欧拉定理

$ans=ai^{Ans_{i+1}\;mod\;\phi(p)+Ans_{i+1}>=\phi(p)?\phi(p):0}$

每层都记录$Ans_{i}$是否对这一层的$p$取过模,用于判断Ans_{i+1}>=\phi(p)

 

特判比较多,注意特判的优先级

1.如果$ai mod p==0$,那么不论接下来是几次幂都返回0

2.如果$ai==1$,那么不论$ai$的多少次幂都是1,同时清空已经取过模的标记

3.如果$i+1$层取过模,那么这一层的运算即使没取模也要标记为取过模,因为实际值一定取模了

4.如果$i+1$层取过模,那么快速幂里需要加上$\phi(p)$,反之$i+1$没取模一定不要加,不然答案是错的

5.接下来在快速幂里更新第i层计算的取模标记

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define NN 501000
  5 #define MM 20001000
  6 #define maxn 20000000
  7 #define ll long long 
  8 #define uint unsigned int
  9 #define ull unsigned long long 
 10 using namespace std;
 11 
 12 int n,m,g,r,root;
 13 int gint()
 14 {
 15     int ret=0,fh=1;char c=getchar();
 16     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 17     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 18     return ret*fh;
 19 }
 20 int use[MM],pr[2000000],phi[MM],cnt;
 21 void Pre()
 22 {
 23     phi[1]=1;
 24     for(int i=2;i<=maxn;i++)
 25     {
 26         if(!use[i]) pr[++cnt]=i,phi[i]=i-1;
 27         for(int j=1;j<=cnt&&i*pr[j]<=maxn;j++){
 28             use[i*pr[j]]=1;
 29             if(i%pr[j]) phi[i*pr[j]]=phi[i]*phi[pr[j]];
 30             else {phi[i*pr[j]]=phi[i]*pr[j];break;}
 31         }
 32     }
 33 }
 34 struct Seg{
 35 ull val[NN<<2],tag[NN<<2];
 36 void pushdown(int rt){
 37     if(!tag[rt]) return;
 38     val[rt<<1]+=tag[rt],val[rt<<1|1]+=tag[rt];
 39     tag[rt<<1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
 40     tag[rt]=0;
 41 }
 42 void update(int L,int R,int l,int r,int rt,int w)
 43 {
 44     if(L<=l&&r<=R){tag[rt]+=w,val[rt]+=w;return;}
 45     int mid=(l+r)>>1;pushdown(rt);
 46     if(L<=mid) update(L,R,l,mid,rt<<1,w);
 47     if(R>mid) update(L,R,mid+1,r,rt<<1|1,w);
 48     //pushup(rt);
 49 }
 50 ull query(int x,int l,int r,int rt)
 51 {
 52     if(l==r) return val[rt];
 53     int mid=(l+r)>>1;pushdown(rt);
 54     if(x<=mid) return query(x,l,mid,rt<<1);
 55     else return query(x,mid+1,r,rt<<1|1);
 56     //pushup(rt);
 57 }
 58 }s;
 59 ull qpow(ull x,ull y,int p,int &fl)
 60 {
 61     ull ans=1;
 62     if(y==0) return 1;
 63     if(x>=p) x%=p,fl=1;
 64     while(y){
 65         if(y&1){
 66             if(ans*x>=p) 
 67                 ans=ans*x%p,fl=1;
 68             else ans=ans*x;
 69         }
 70         if(x*x>=p)
 71             x=x*x%p,fl=1;
 72         else x=x*x;
 73         y>>=1;
 74     }return ans;
 75 }
 76 ull euler(int i,int ma,int p,int &fl)
 77 {
 78     ull ai=s.query(i,1,n,1);
 79     if(p==1) {fl=1;return 0;}
 80     if(ai>=p) fl=1;
 81     if(ai%p==0) return 0;
 82     if(ai==1) {fl=0;return 1;}
 83     int o=0;ai%=p;
 84     if(i==ma) return ai;
 85     ull ans=euler(i+1,ma,phi[p],o);
 86     if(o==1) fl=1; 
 87     /*if(ans==0){
 88         if(o){
 89             if(ai%p==0) {return 0;}
 90             else return qpow(ai,ans+phi[p],p,fl);
 91         }else{
 92             return 1;
 93         }
 94     }else{
 95         if(o) return qpow(ai,ans+phi[p],p,fl);
 96         else return qpow(ai,ans,p,fl);
 97     }*/
 98     if(ans==0&&o&&ai==0) return 0;
 99     else if(o) return qpow(ai,ans+phi[p],p,fl);
100     else return qpow(ai,ans,p,fl);
101 }
102 
103 int main()
104 {
105     //freopen("t2.in","r",stdin);
106     //freopen("testdata.in","r",stdin);
107     //freopen("a.out","w",stdout);
108     int fl,x,y,z;
109     scanf("%d%d",&n,&m);
110     Pre();
111     for(int i=1;i<=n;i++)
112         x=gint(),s.update(i,i,1,n,1,x);
113     for(int i=1;i<=m;i++)
114     {
115         fl=gint(),x=gint(),y=gint(),z=gint();
116         if(fl==1){
117             s.update(x,y,1,n,1,z);
118         }else{
119             int fl=0;
120             printf("%llu\n",euler(x,y,z,fl));
121         }
122     }
123     return 0;
124 }