题解 P3747 【[六省联考2017]相逢是问候】

devout · 2020-04-06 19:19:45 · 题解

博客内食用更佳

看到区间修改区间查询，大家一定会觉得这是一个线段树题

然后再看修改操作a_i=c^{a_i}

这玩意真的能用线段树维护吗？？？

答案是：显然不能

那怎么办呢？

看到这么多落在一起的幂，好多还都一样(c)，我们可以联想到这道题所以我们可以用扩展欧拉定理推一下，顺便给自己的博客打广告嘤嘤嘤~

根据扩展欧拉定理：a^c\equiv a^{c\bmod \phi(p)+\phi(p)}\bmod p

那么经过一段时间，当\phi(\phi(\phi(\phi(...\phi(\phi(p))))))=1之后，我们的式子就变成了c^{c^{c...^c}}，就和a_i无关了！！！

于是我们又想到了这道题，采取一样的做法，对于修改，暴力修改如果修改到\phi(\phi(\phi(\phi(...\phi(\phi(p))))))=1之后就不管他了

可以证明，最多经过2\log p次之后，\phi(\phi(\phi(\phi(...\phi(\phi(p))))))=1，也就是说每个点最多会被修改2\log p次，而每次修改最多需要\log次递归，每次递归的时候需要\log的时间来算快速幂，也就是说这道题我们就做出了一种O(m\log^3 p)的做法

然后我们手推一下就会发现5\times 10^4\times \log^3 (5\times10^8)\approx4\times 10^9显然是跑不过去的，但是能够拿到80分，但是因为这题标程出锅了，所以数据特别水，所以实际能够拿到90。

但是注意这里有一个细节，因为扩展欧拉定理只有在指数c\geq \phi(p)的时候才成立，所以我们要判断一下要不要加上\phi(p)，这里可以用一个flag变量来求

因为接下来要用到的光速幂的优化可能有人之前没有学过（比如说我），所以本来应该贴一下代码的，但是因为考虑到洛谷题解的篇幅限制，大家可以去我的博客里面去看90分代码

那么我们考虑怎么优化

我们发现我们每次暴力求答案的时候，底数是一样的，而模数也不多 所以我们可以对于每个模数进行一下光速幂（继续打广告）然后我们可以优化掉一个\log变成O(m\log^2p)就解决了

同时我们也要在预处理的时候处理一下有没有溢出的情况（在做的过程中出现了\geq\phi(p)），如果有就加上\phi(p)

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=1e5+5;
const int bl=10000;
const int M=65;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

# define int long long

int n,m,p,c;
int a[N];
int phi[N],dep;
int qpow[bl+5][M][2];
bool flag,over[bl+5][M][2];

struct segment_tree{
    int l,r;
    int sum,tim;
}seg[N<<2];

# define lc (u<<1)
# define rc (u<<1|1)

int getphi(int x){
    int res=x;
    for(int i=2;1ll*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 init(){
    int x=p;
    phi[0]=x;
    while(x>1){
        x=getphi(x);
        phi[++dep]=x;//只处理会用到的phi
    }
    phi[++dep]=1;
    Rep(i,0,dep){
        qpow[0][i][0]=1;
        Rep(j,1,bl){
            qpow[j][i][0]=qpow[j-1][i][0]*c;//预处理
            if(qpow[j][i][0]>=phi[i])over[j][i][0]=true,qpow[j][i][0]%=phi[i];
            over[j][i][0]|=over[j-1][i][0];//处理有没有溢出
        }
    }
    Rep(i,0,dep){
        qpow[0][i][1]=1;
        Rep(j,1,bl){
            qpow[j][i][1]=qpow[j-1][i][1]*qpow[bl][i][0];//预处理
            if(qpow[j][i][1]>=phi[i])over[j][i][1]=true,qpow[j][i][1]%=phi[i];
            over[j][i][1]|=over[j-1][i][1];//溢出
        }
    }
}

int Qpow(int ind,int p){
    flag|=over[ind%bl][p][0]|over[ind/bl][p][1];
    int res=qpow[ind%bl][p][0]*qpow[ind/bl][p][1];//计算
    if(res>=phi[p])flag=true,res%=phi[p];//在乘的时候溢出也算
    return res;
}

int calc(int id,int lim,int d){
    flag=false;
    if(d==lim){
        if(a[id]>=phi[d]){
            flag=true;
            return a[id]%phi[d];
        }
        return a[id];
    }
    int x=calc(id,lim,d+1);//递归求解，同上帝那道题
    if(flag)x+=phi[d+1],flag=false;
    return Qpow(x,d);
}

void pushup(int u){
    seg[u].sum=(seg[lc].sum+seg[rc].sum)%p;
    seg[u].tim=min(seg[lc].tim,seg[rc].tim);
}

void build(int u,int l,int r){
    seg[u].l=l,seg[u].r=r;
    if(l==r){
        seg[u].sum=a[l];
        seg[u].tim=0;
        return;
    }
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(u);
}

void update(int u,int l,int r){
    if(seg[u].tim>=dep)return;
    if(seg[u].l==seg[u].r){
        seg[u].tim++;
        seg[u].sum=calc(seg[u].l,seg[u].tim,0);//暴力修改
        return;
    }
    int mid=seg[u].l+seg[u].r>>1;
    if(l<=mid)update(lc,l,r);
    if(r>mid)update(rc,l,r);
    pushup(u);
}

int query(int u,int l,int r){
    if(seg[u].l>=l&&seg[u].r<=r)return seg[u].sum;
    int mid=seg[u].l+seg[u].r>>1;
    int res=0;
    if(l<=mid)res+=query(lc,l,r);
    if(r>mid)res+=query(rc,l,r);
    res%=p;
    return res;
}

signed main()
{
    read(n),read(m),read(p),read(c);
    Rep(i,1,n)read(a[i]);
    init();
    build(1,1,n);
    Rep(i,1,m){
        int opt,x,y;
        read(opt),read(x),read(y);
        if(!opt)update(1,x,y);
        else printf("%lld\n",query(1,x,y));
    }
    return 0;
}