2017六省联考 相逢是问候

题目链接：戳我

落谷时间卡得真紧。。。。test9 和test11 根本过不去，只有在BZOJ上面A掉了。。。。。。

首先可以看得出这是一个线段树维护的数据结构题目吧qwqwq

但是对于这种阶乘修改，显然是不具备可加性的，所以我们只能暴力修改。。。。但是暴力修改时间复杂度是会炸天的！

但是我们再看一下——

\(c^{a[i]^{a[i]^{...}}} \pmod p\)
我们想到了什么！！！——拓展欧拉定理啊qwqwq

\[a^b\equiv\begin{cases}a^{b\%\phi(p)}&{gcd(a,p)=1}\\a^b&{gcd(a,p)1,b\le\phi(p)}\\a^{b\%\phi(p)+\phi(p)}&gcd(a,p)\neq1,b\ge\phi(p)\end{cases}\pmod p\]

（其实大家可以先去看看【上帝与集合的正确用法】这个题，想必是有一些启发的）

根据拓展欧拉定理，显然我们递归几次这个模数就会变成1，当模数变成1的时候，显然就不需要再次计算了。

举个例子：
\[c^{a[i]^{a[i]}}=c^{a[i]^{a[i]\%\phi(\phi(p))+\phi(\phi(p))}+\phi(p)}\]

所以我们可以预先处理出来p的phi值都是多少，结束条件为phi值==1。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,c,p,cnt;
int a[MAXN],phi[MAXN];
struct Node{int l,r,tot,sum;}t[MAXN<<2];

inline int Phi(int x)
{
    long long cur_ans=x;
    int now=x;
    for(int i=2;i*i<=now;i++)
    {
        if(now%i==0) cur_ans=cur_ans/i*(i-1);
        while(now%i==0) now/=i;
    }
    if(now>1) cur_ans=cur_ans/now*(now-1);
    return cur_ans;
}

inline void init()
{
    int cur=p;
    while(cur>1)
    {
        cur=Phi(cur);
        phi[++cnt]=cur;
    }
    //for(int i=1;i<=cnt;i++) printf("phi[%d]=%d\n",i,phi[i]);
}

inline long long fpow(long long x,long long y,long long mod)
{
    long long cur_ans=1;
    int flag1=0,flag2=0;
    while(y)
    {
        if(y&1) cur_ans=cur_ans*x,flag1|=flag2;
        if(cur_ans>=mod) flag1=1,cur_ans%=mod;
        x=x*x;
        if(x>=mod) flag2=1,x%=mod;
        y>>=1;
    }
    if(flag1) cur_ans+=mod;
    return cur_ans;
}

inline long long solve(int l,int r,long long x,long long mod)
{
    if(l==r) return x;
    return fpow(c,solve(l+1,r,x,phi[l+1]),mod);
}

inline int ls(int x){return x<<1;}

inline int rs(int x){return x<<1|1;}

inline void push_up(int x)
{   
    t[x].sum=(t[ls(x)].sum+t[rs(x)].sum)%p;
    t[x].tot=min(t[ls(x)].tot,t[rs(x)].tot);
}

inline void build(int x,int l,int r)
{
    t[x].l=l,t[x].r=r;
    if(l==r){t[x].sum=a[l];return;}
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    push_up(x);
}

inline void update(int x,int ll,int rr)
{
    if(t[x].tot>cnt) return;
    int l=t[x].l,r=t[x].r;
    if(l==r)
    {
        t[x].sum=solve(0,++t[x].tot,a[l],p)%p;
        return;
    }
    int mid=(l+r)>>1;
    if(ll<=mid) update(ls(x),ll,rr);
    if(mid<rr) update(rs(x),ll,rr);
    push_up(x);
}

inline long long query(int x,int ll,int rr)
{
    int l=t[x].l,r=t[x].r;
    if(ll<=l&&r<=rr) return t[x].sum%p;
    int mid=(l+r)>>1;
    long long cur_ans=0;
    if(ll<=mid) cur_ans=(cur_ans+query(ls(x),ll,rr))%p;
    if(mid<rr) cur_ans=(cur_ans+query(rs(x),ll,rr))%p;
    return cur_ans;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d%d%d%d",&n,&m,&p,&c);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    init();
    //for(int i=1;i<=cnt;i++) printf("%d\n",phi[i]);
    for(int i=1;i<=m;i++)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==0) update(1,l,r);
        else printf("%lld\n",query(1,l,r));
    }
    return 0;   
}

2017六省联考 相逢是问候

原文：https://www.cnblogs.com/fengxunling/p/10501979.html