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这一层？

2017.07.04:如果a和m互质的话是只能用欧拉定理而不能用ext的，所以一定要加一个判断，大家如果没有A掉问题可能是出在这里…

另外在Exbilar同学的提醒下代码做出了一些改动

#include
     
      #include
      
       #include
       
        #include
        
         #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;}inline LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;}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(gcd(c,res)!=1)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;}