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

Luan_233 · 2018-11-17 21:37:26 · 题解

Solution

• 这真是一道浪费时间浪费生命的好题啊！我从11月8号踏上去秦皇岛的征途时，在火车上和SGCollin一起搞这道题，直到现在才把这题搞掉。果然还是自己太菜了。

• 如果没有做过P4139 上帝与集合的正确用法建议先去做一做，别看这是个紫牌题，其实核心代码超级短。具体来讲，你只需要一个线性筛法，一个快速幂，一个dfs跑扩展欧拉定理就做完了。

• 扩展欧拉定理不必多说，注意好它的分类讨论情况，即指数是否比\varphi(p)大，若指数比\varphi(p)小则无法进入指数循环节，不能用 a^k \equiv a^{k \% \varphi(p)+\varphi(p) } \ (mod \ p) ，但是在那个紫牌题中，显然 2^{2^{2^{......}} } 是比\varphi(p)要大的多的，所以定理最后一条可以直接用。

• 很显然每一次的模数都会变为它自己的欧拉函数，而这个过程的次数不会超过对数级别。有一个简单的证明，根据欧拉函数的公式，可以看到一个偶数在求欧拉函数时，一定会把一个素因子2提出来变成1，也就是至少除以2，而一个奇数一定会把自己的一个奇质因子提出来减1，变成一个偶数，接下来就是重复以上过程，直到模数变成1为止。这时任意实数模1都是0，直接返回就好。故P4139的核心代码如下：

inline int dfs(int mod){
    if(mod==1) return 0;
    return quick_pow(2,dfs(phi[mod])+phi[mod],mod);
}

• 我们看这道题，c^{c^{c^{......}}} mod \ p可以转化为c^{c^{c^{......}} \ mod \ \varphi(p)+\varphi(p)} mod \ p ，然后再计算 c^{c^{c^{......}}} \ mod \ \varphi(p) ，这又可以转化为 c^{c^{c^{......}} \ mod \ \varphi(\varphi(p))+\varphi(\varphi(p))} mod \ \varphi(p) ，如此反复嵌套，根据上面提到的东西，它至多进行对数级别层，也就是说只有这几层会对答案产生影响。

• 还有一道题，P4145 上帝造题的七分钟2 / 花神游历各国。为什么要提这道题呢？注意到题目中的操作不具有区间性质，但是 c^{c^{c^{......}}} mod \ p 的值，在指数的层数达到一定值以后就不再变化，就变成了上面提到的这个过程，并且对数很小，可以考虑维护其单点修改次数，修改时直接暴力，达到临界条件后就不再更改。与这道蓝牌题的思路就很相似。

• 回到这道题，上面的东西综合起来就是这题的正解算法。考虑线段树，维护一个区间的最小修改次数。由于我们要用到的欧拉函数的数目很少，可以直接暴力算出来，修改时的power \ tower直接暴算到底，快速幂时加上一点特判，就可以判断扩展欧拉定理运用的两个条件，也就是：

typedef long long LL;

inline LL qpow(LL t,LL mod){
    LL val=1,a=c;
    flag=0;
    while(t){
        if(t&1) val=val*a;
        a=a*a;
        t>>=1;
        if(val>=mod) val%=mod,flag=1;
        if(a>=mod) a%=mod;
    }
    return val;
}

• 然后单次修改的复杂度就是 序列操作\times递归层数\times快速幂，达到了三个\log，复杂度比较高，常数大的会被第9、11两个点卡T（我吸了氧把第9个点过了，恩）。

• 然后就是最终的优化。根据网上说法，欧拉函数很少，意味着模数很少，考虑将快速幂预处理，分为c^{i}\ (mod \ p) 与 c^{10000 \times i} \ (mod \ p)，查询时直接将两块进行拼接，上面的特判用一个bool数组存下来，就可以少掉一个\log了。然后加读优、inline，再写的美观一些，就足以通过此题。

Code

#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

#define M 55
#define maxn 100005

using namespace std;

typedef unsigned long long LL;

template<typename T> inline void read(T &x){
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

int n,m,mint,ls[maxn],rs[maxn],ti[maxn],cnt;

LL p,c,pow1[maxn][M],pow2[maxn][M],v[maxn],val[maxn],phi[M];

bool flag,b1[maxn][M],b2[maxn][M];

inline LL calc_phi(LL vi){
    LL ret=vi,tmp=vi,lim=sqrt(vi);
    for(LL i=2;i<=lim;++i){
        if(!(tmp%i)){
            ret=ret*(i-1)/i;
            while(!(tmp%i)) tmp/=i;
        }
    }
    if(tmp>1) ret=ret*(tmp-1)/tmp;
    return ret;
}

inline void pre_work(){
    LL tmp=p; phi[0]=p;
    while(tmp!=1) tmp=calc_phi(tmp),phi[++mint]=tmp;
    phi[++mint]=1;
    for(int i=0;i<=mint;++i){
        pow1[0][i]=1;
        for(int j=1;j<=10000;++j){
            pow1[j][i]=pow1[j-1][i]*c;
            if(pow1[j][i]>=phi[i]) pow1[j][i]%=phi[i],b1[j][i]=1;
            b1[j][i]|=b1[j-1][i];
        }
    }
    for(int i=0;i<=mint;++i){
        pow2[0][i]=1;
        b2[1][i]=b1[10000][i];
        for(int j=1;j<=10000;++j){
            pow2[j][i]=pow2[j-1][i]*pow1[10000][i];
            if(pow2[j][i]>=phi[i]) pow2[j][i]%=phi[i],b2[j][i]=1;
            b2[j][i]|=b2[j-1][i];
        }
    }
}

inline LL calc(LL v,LL id){
    flag=0;
    LL v1=v%10000,v2=v/10000,ret=pow1[v1][id]*pow2[v2][id];
    if(ret>=phi[id]) ret=ret%phi[id],flag=1;
    flag|=b1[v1][id]|b2[v2][id];
    return ret;
}

inline LL dfs(LL vi,int deep,int lim){
    flag=0;
    if(deep==lim){
        if(vi>=phi[deep]) flag=1,vi%=phi[deep];
        return vi;
    }
    LL ci=dfs(vi,deep+1,lim);
    return calc(flag?ci+phi[deep+1]:ci,deep);
}

inline void build(int L,int R,int cur){
    if(L==R){ read(v[cur]); val[cur]=v[cur]; return ; }
    int mid=(L+R)>>1;
    ls[cur]=++cnt; build(L,mid,ls[cur]);
    rs[cur]=++cnt; build(mid+1,R,rs[cur]);
    val[cur]=val[ls[cur]]+val[rs[cur]];
    if(val[cur]>=p) val[cur]-=p;
}

inline void update(int L,int R,int l,int r,int cur){
    if(ti[cur]>=mint) return ;
    if(L==R){
        ++ti[cur]; val[cur]=dfs(v[cur],0,ti[cur]);
        return ;
    }
    int mid=(L+R)>>1;
    if((l<=mid)&&(ti[ls[cur]]<mint)) update(L,mid,l,r,ls[cur]);
    if((r>mid)&&(ti[rs[cur]]<mint)) update(mid+1,R,l,r,rs[cur]);
    val[cur]=val[ls[cur]]+val[rs[cur]];
    if(val[cur]>=p) val[cur]-=p;
    ti[cur]=min(ti[ls[cur]],ti[rs[cur]]);
}

inline LL query(int L,int R,int l,int r,int cur){
    if((l<=L)&&(R<=r)) return val[cur];
    int mid=(L+R)>>1; LL ret=0;
    if(l<=mid) ret=query(L,mid,l,r,ls[cur]);
    if(r>mid) ret+=query(mid+1,R,l,r,rs[cur]);
    return (ret>=p)?(ret-p):ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    read(n); read(m); read(p); read(c);
    build(1,n,++cnt); pre_work();
    while(m--){
        int opt,l,r;
        read(opt); read(l); read(r);
        if(opt==0) update(1,n,l,r,1);
        else if(opt==1) cout<<query(1,n,l,r,1)<<endl;
    }
    return 0;
}