BZOJ5394: [Ynoi2016]炸脖龙(欧拉广义降幂)

就是让你求这个：

传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=5394

解题思路：

NOIP2018后第一道题，感觉非常像那个上帝与集合的正确用法。

具体来说就是使用递归的求解方式，不过这次和上帝与集合的正确用法不同的是：

1.这次不是无限项，所以可以不在p=0时停止。

2.因为被取模数有限大，所以要特判小于φ(p)的情况。

3.询问时要预先处理φ(p)

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lll spc<<1
  5 #define rrr spc<<1|1
  6 #define maxval 20000000
  7 typedef long long lnt;
  8 struct trnt{
  9     lnt val;
 10     lnt lzt;
 11 }tr[2000000];
 12 int prime[20000001];
 13 int eula[20000001];
 14 bool vis[20000001];
 15 int cnt;
 16 int n,m;
 17 lnt a[600000];
 18 lnt read(void)
 19 {
 20     lnt ans=0;
 21     lnt f=1;
 22     char ch=getchar();
 23     while(ch<'0'||ch>'9')
 24     {
 25         if(ch=='-')
 26             f=-f;
 27         ch=getchar();
 28     }
 29     while(ch<='9'&&ch>='0')
 30     {
 31         ans=ans*10ll+(lnt)(ch-'0');
 32         ch=getchar();
 33     }
 34     return ans*f;
 35 }
 36 void Get_prime(void)
 37 {
 38     for(int i=2;i<=maxval;i++)
 39     {
 40         if(!vis[i])
 41         {
 42             prime[++cnt]=i;
 43             eula[i]=i-1;
 44         }
 45         vis[i]=false;
 46         for(int j=1;j<=cnt&&(i*prime[j]<=maxval);j++)
 47         {
 48             vis[i*prime[j]]=true;
 49             if(i%prime[j]==0)
 50             {
 51                 eula[i*prime[j]]=eula[i]*prime[j];
 52                 break;
 53             }
 54             eula[i*prime[j]]=eula[i]*(prime[j]-1);
 55         }
 56     }
 57     return ;
 58 }
 59 void Add(int spc,int l,int r,lnt v)
 60 {
 61     tr[spc].val+=v*(lnt)(r-l+1);
 62     tr[spc].lzt+=v;
 63     return ;
 64 }
 65 void pushup(int spc)
 66 {
 67     tr[spc].val=tr[lll].val+tr[rrr].val;
 68     return ;
 69 }
 70 void pushdown(int spc,int l,int r)
 71 {
 72     if(tr[spc].lzt)
 73     {
 74         int mid=(l+r)>>1;
 75         Add(lll,l,mid,tr[spc].lzt);
 76         Add(rrr,mid+1,r,tr[spc].lzt);
 77         tr[spc].lzt=0;
 78     }
 79     return ;
 80 }
 81 void build(int l,int r,int spc)
 82 {
 83     if(l==r)
 84     {
 85         tr[spc].val=a[l];
 86         return ;
 87     }
 88     int mid=(l+r)>>1;
 89     build(l,mid,lll);
 90     build(mid+1,r,rrr);
 91     pushup(spc);
 92     return ;
 93 }
 94 void update(int l,int r,int ll,int rr,int spc,lnt v)
 95 {
 96     if(ll>r||l>rr)
 97         return ;
 98     if(ll<=l&&r<=rr)
 99     {
100         Add(spc,l,r,v);
101         return ;
102     }
103     int mid=(l+r)>>1;
104     pushdown(spc,l,r);
105     update(l,mid,ll,rr,lll,v);
106     update(mid+1,r,ll,rr,rrr,v);
107     pushup(spc);
108     return ;
109 }
110 lnt query(int l,int r,int spc,int pos)
111 {
112     if(l==r)
113         return tr[spc].val;
114     int mid=(l+r)>>1;
115     pushdown(spc,l,r);
116     if(pos<=mid)
117         return query(l,mid,lll,pos);
118     return query(mid+1,r,rrr,pos);
119 }
120 lnt ksm(lnt a,lnt b,lnt mod,int plc)
121 {
122     lnt ans=1;
123     while(b)
124     {
125         if(b&1)
126         {
127             ans=ans*a;
128             if(ans>=mod)
129             {
130                 ans%=mod;
131                 vis[plc]=true;
132             }
133         }
134         a=a*a;
135         if(a>=mod)
136         {
137             a%=mod;
138             vis[plc]=true;
139         }
140         b/=2;
141     }
142     return ans;
143 }
144 lnt Query(int l,int r,int p)
145 {
146     vis[l]=false;   
147     lnt tmp=query(1,n,1,l);
148     if(tmp>=p)
149         vis[l]=true;
150     tmp%=p;
151     if(tmp==1)
152         return 1;
153     if(p==1)
154         return 0;
155     if(l==r)
156         return tmp%p;
157     lnt temp=eula[p];
158     return ksm(tmp,Query(l+1,r,temp)+vis[l+1]*temp,p,l);
159 }
160 int main()
161 {
162     Get_prime();
163     n=read();
164     m=read();
165     for(int i=1;i<=n;i++)
166         a[i]=read();
167     build(1,n,1);
168     while(m--)
169     {
170         lnt cmd=read(),l=read(),r=read(),x=read();
171         if(cmd==1)
172             update(1,n,l,r,1,x);
173         else
174             printf("%lld
",Query(l,r,x));
175     }
176     return 0;
177 }