首页 > 代码库 > [BZOJ 4869][SXOI2017]相逢是问候（扩展欧拉定理+线段树）
[BZOJ 4869][SXOI2017]相逢是问候（扩展欧拉定理+线段树）
Description
Informatik verbindet dich und mich.
信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以
分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是
输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为
这个结果可能会很大，所以你只需要输出结果mod p的值即可。
Solution
强迫症非要把这两道题放在一起…
学习了一下扩展欧拉定理
a^b≡x(mod m) 求x
gcd(a,m)=1，欧拉定理：a^b≡a^(b%φ(m))(mod m)
gcd(a,m)>1，且b>φ(m)，扩展欧拉定理：a^b≡a^(b%φ(m)+φ(m))(mod m)
（b<=φ(m)时，直接用a^b求就可以了）
考试的时候数据出了一点问题啊…不过及时解决了也没造成太大影响
数据出错的原因据说是因为没有多展开phi[1]=1这一层？
cx≡cx%φ(p)+φ(p)(mod
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define MAXN 50005using namespace std;typedef long long LL; int n,m,P,c,a[MAXN],phi[MAXN],k;struct Node{ int l,r,cnt; LL sum;}t[MAXN*4];inline int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}inline int get_phi(int x){ int res=x; for(int i=2;i*i<=x;i++) { if(x%i==0) { res=res/i*(i-1); while(x%i==0)x/=i; } } if(x!=1)res=res/x*(x-1); return res;}void build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r,t[idx].cnt=0; if(l==r){t[idx].sum=a[l]%phi[0];return;} int mid=(l+r)>>1; build(idx<<1,l,mid); build(idx<<1|1,mid+1,r); t[idx].sum=(t[idx<<1].sum+t[idx<<1|1].sum)%phi[0];}int query(int idx,int l,int r){ if(l<=t[idx].l&&r>=t[idx].r)return t[idx].sum; int mid=(t[idx].l+t[idx].r)>>1; if(r<=mid)return query(idx<<1,l,r); else if(l>mid)return query(idx<<1|1,l,r); else return (query(idx<<1,l,r)+query(idx<<1|1,l,r))%phi[0];}inline LL pow(LL a,LL n,LL mod){ LL res=1; while(n) { if(n&1)res=(res*a)%mod; a=(a*a)%mod; n>>=1; } return res%mod;}inline LL modify(int cnt,LL num){ LL res=num; if(res>=phi[cnt])res=res%phi[cnt]+phi[cnt]; for(int i=cnt;i>0;i--) { res=pow(c,res,phi[i-1]); if(!res)res+=phi[i-1]; } return res%phi[0];} void change(int idx,int l,int r){ if(t[idx].cnt>=k)return; if(t[idx].l==t[idx].r) { t[idx].cnt++; t[idx].sum=modify(t[idx].cnt,a[t[idx].l]); return; } int mid=(t[idx].l+t[idx].r)>>1; if(r<=mid)change(idx<<1,l,r); else if(l>mid)change(idx<<1|1,l,r); else change(idx<<1,l,r),change(idx<<1|1,l,r); t[idx].sum=(t[idx<<1].sum+t[idx<<1|1].sum)%phi[0]; t[idx].cnt=min(t[idx<<1].cnt,t[idx<<1|1].cnt);}int main(){ n=read(),m=read(),P=read(),c=read(); for(int i=1;i<=n;i++)a[i]=read(); k=0;phi[0]=P; while(P!=1) { phi[++k]=get_phi(P); P=phi[k]; } phi[++k]=1; build(1,1,n); for(int i=1;i<=m;i++) { int opt=read(),l=read(),r=read(); if(!opt)change(1,l,r); else printf("%d\n",query(1,l,r)); } return 0;}
[BZOJ 4869][SXOI2017]相逢是问候（扩展欧拉定理+线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。