bzoj4869：[shoi2017]相逢是问候——题解

关键词：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<map>
using namespace std;
typedef long long ll;
const int N=5e4+5;
const int O=1e4+5;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct tree{
    ll v,t;
}tr[N*4];
int su[O],he[O],cnt,phi[40],n,m;
ll p,c,logp,b[N];
bool ok;
inline ll qpow(ll k,int p){
    ll ans=1,s=c;
    while(k){
        if(k&1)ans=ans*s;
        s*=s;k>>=1;
        if(s>=p)ok=1,s%=p;
        if(ans>=p)ok=1,ans%=p;
    }
    return ans;
}
int Euler(int k){
    int res=k;
    for(int i=1;su[i]*su[i]<=k;i++){
        if(k%su[i]==0){
            res-=res/su[i];
            while(k%su[i]==0)k/=su[i];
        }
    }
    if(k>1)res-=res/k;
    return res;
}
void prime(){
    for(int i=2;i<O;i++){
        if(he[i]==0){
            cnt++;
            su[cnt]=i;
        }
        for(int j=1;j<=cnt&&i*su[j]<O;j++){
            he[su[j]*i]=1;
            if(i%su[j]==0)break;
        }
    }
    phi[logp]=p;
    while(phi[logp]!=1)phi[++logp]=Euler(phi[logp-1]);
    phi[++logp]=1;
}
void build(int a,int l,int r){
    if(l==r){
        tr[a].v=b[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(a<<1,l,mid);build(a<<1|1,mid+1,r);
    tr[a].v=(tr[a<<1].v+tr[a<<1|1].v)%p;  
}
ll suan(ll v,ll k){
    ll tmp=v;
    if(tmp>phi[k])tmp=tmp%phi[k]+phi[k];
    for(int i=k;i>0;i--){
        ok=0;tmp=qpow(tmp,phi[i-1]);
        if(ok)tmp+=phi[i-1];
    }
    return tmp;
}
void gai(int a,int l,int r,int l1,int r1){
    if(tr[a].t>=logp)return;
    if(r<l1||r1<l)return;
    if(l==r){
        tr[a].t++;
        tr[a].v=suan(b[l],tr[a].t);
        return;
    }
    int mid=(l+r)>>1;
    gai(a<<1,l,mid,l1,r1);gai(a<<1|1,mid+1,r,l1,r1);
    tr[a].v=(tr[a<<1].v+tr[a<<1|1].v)%p;
    tr[a].t=min(tr[a<<1].t,tr[a<<1|1].t);
}
ll wen(int a,int l,int r,int l1,int r1){
    if(r<l1||r1<l)return 0;
    if(l1<=l&&r<=r1)return tr[a].v;
    int mid=(l+r)>>1;
    return (wen(a<<1,l,mid,l1,r1)+wen(a<<1|1,mid+1,r,l1,r1))%p;
}
int main(){
    n=read(),m=read(),p=read(),c=read();
    prime();
    for(int i=1;i<=n;i++)b[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op=read(),l=read(),r=read();
        if(!op)gai(1,1,n,l,r);
        else printf("%lld\n",wen(1,1,n,l,r));
    }
    return 0;
}

bzoj4869[shoi2017]相逢是问候

可以发现，\[\displaystylec^c^c^\cdots\]从下到上对应的模数是\(p,\varphi(p),\varphi(\varphi(p)),\varphi(\varphi(\varphi(p))),\ldots,1,1\)。（为什么有两个\(1\)？一会儿再说）因此当一个数被修改了很多次以后它就不会再变了，维护一下一个数被修改... 查看详情

bzoj4869[shoi2017]相逢是问候

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4869【题解】发现好像没有办法普通维护。给小盆友们江数论的时候江过x^mmodp=x^(mmodphi(p))modp发现一个数进行phi操作最多log次。暴力就行啦qwq注意就是phi的那个最后要补一个phi[++pn]=1。... 查看详情

bzoj4869：[shoi2017]相逢是问候——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=4869题面复制于洛谷：https://www.luogu.org/problemnew/show/P3747#sub 参考洛谷的前两篇（也是仅有的两篇）题解。首先我们要知道一个公式：这又被叫做扩展欧拉定理，证明我们并不关心。有了扩展... 查看详情

bzoj4869[shoi2017]相逢是问候

DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：0lr表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai... 查看详情

bzoj4869[shoi2017]相逢是问候线段树+扩展欧拉定理(代码片段)

DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：0lr表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai... 查看详情

[bzoj4869][六省联考2017]相逢是问候(线段树+扩展欧拉定理)

4869:[Shoi2017]相逢是问候TimeLimit:40Sec  MemoryLimit:512MBSubmit:1313  Solved:471[Submit][Status][Discuss]DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到 查看详情

bzoj千题计划271：bzoj4869:[六省联考2017]相逢是问候(代码片段)

http://www.lydsy.com/JudgeOnline/problem.php?id=4869 欧拉降幂+线段树，每个数最多降log次，模数就会降为1 #include<cmath>#include<cstdio>#include<iostream>usingnamespacestd;#defineN50001intn,m,p,c; 查看详情

[bzoj4869][sxoi2017]相逢是问候（扩展欧拉定理+线段树）

DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：0lr表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai... 查看详情

bzoj4869相逢是问候（线段树，欧拉定理）

【BZOJ4869】相逢是问候（线段树，欧拉定理）题面BZOJ题解根据欧拉定理递归计算（类似上帝与集合的正确用法)所以我们可以用线段树维护区间最少的被更新的多少次如果超过了(varphi)的限制就不用再计算了如果需要计算就每次暴... 查看详情

bzoj4869相逢是问候[线段树]

相逢是问候TimeLimit:40Sec  MemoryLimit:512MB[Submit][Status][Discuss]Description　　Informatikverbindetdichundmich.　　信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以　　分为两... 查看详情

[shoi2017]相逢是问候

Description信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：0lr表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是输入的一... 查看详情

[六省联考2017]相逢是问候

相逢是问候2017-09-09DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：0lr表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai... 查看详情

[六省联考2017]相逢是问候

题链SOL：p与a不互质时，设c=bmodφ(p)（专门设出来是因为公式不能正常显示），如果b>=φ(p)：a^b≡a^(c+φ(p))（注意b<φ(p)的时候再减φ(p)）我们可以证明  φ(p)在log次迭代后到达1，以后的数就不会对答案产... 查看详情

洛谷p3747[六省联考2017]相逢是问候(代码片段)

传送门题解扩展欧拉定理。线段树维护，已经全改到底了的节点就不管，不然暴力修改下去。//Achen#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<vector>#include<cstdio>#include<q 查看详情

p3747相逢是问候欧拉定理+线段树(代码片段)

巨难!!!去年六省联考唯一的一道黑牌题，我今天一天从早到晚，把它从暴力15分怼到了90分，极端接近正解了。bzoj上A了，但是洛谷和loj上面就不行。伪正解会T，奇奇怪怪的类正解会WA。。那么，网上的题解多得很，我就不细说了... 查看详情

p3747[六省联考2017]相逢是问候(代码片段)

题意如果对一个数操作(k)次，那么这个数会变成(c^c^...^a_i)，其中(c)有(k)个。根据P4139上帝与集合的正确用法这道题，我们可以知道一个数不断变为自己的欧拉函数，大约(log)次就会变成1，而任何数模(1)都是(0)，于是我们可以用势... 查看详情

bzoj4872:[shoi2017]分手是祝愿(代码片段)

4872:[Shoi2017]分手是祝愿DescriptionZeitundRaumtrennendichundmich.时空将你我分开。B君在玩一个游戏，这个游戏由n个灯和n个开关组成，给定这n个灯的初始状态，下标为从1到n的正整数。每个灯有两个状态亮和灭，我们用1来表示这个灯是亮... 查看详情

bzoj4872:[shoi2017]分手是祝愿(代码片段)

一早上膝盖跪烂了ORZ出门右转膜题解谢谢#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>usingnamespacestd;typedeflonglongLL;consti 查看详情