emm

Problem

https://www.luogu.org/problemnew/show/P3934

Solution

扩展欧拉定理：
$$a^b\equiv \begin{cases} &a^{b\%\varphi(p)} &\gcd(a,p)=1\\ &a^b &\gcd(a,p)\neq1,b<\phi(p)\\ &a^{b\%\varphi(p)+\varphi(p)} &\gcd(a,p)\neq1,b\geq\phi(p) \end{cases}\pmod p$$

可以证明如此递归 mod 下去，模数会在 $\log$ 层的递归之后变为 1。因此暴力递归计算是 $\log n$ 级的。

但是我们可能并不知道上面的 $b$ 是否是大于 $\phi(p)$ 的。

我们发现假设我们递归到 $l$ 层，往后看五个数。如果中间出现了 $1$，则终点到达。

否则至少会是 $2^{2^{2^{2^{2}}}}>>p$。

因此稍微超前算一下就行了。

复杂度 $\text{O( 玄学)}$。

Solution

// Code by ajcxsu
// Problem: nephren

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

template<typename T> void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=5e5+10, M=2e7+10;
typedef long long ll;
ll pri[M], p, phi[M];
bool npri[M];


#define lowbit(x) x&-x
ll C[N];
void updata(int x, ll d) {
    while(x<N) {
        C[x]+=d;
        x+=lowbit(x);
    }
}
ll query(int x) {
    ll ret=0;
    while(x) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

ll qpow(ll x, ll y, ll mo) {
    ll ret=1;
    x%=mo;
    while(y) {
        if(y&1ll) ret=(ret*x) % mo;
        x=(x*x) % mo, y>>=1ll;
    }
    return ret;
}

ll cac(int l, int r, ll mo) {
    if(mo==1) return 0;
    if(l==r) return query(r)%mo;
    int f=min(l+5, r);
    for(int i=l+1;i<=f;i++) if(query(i)==1) f=i;
    ll last=query(f), q=0;
    for(int i=f-1;i>l;i--) {
        q=last, last=1;
        while(q--) {
            last*=query(i);
            if(last>=phi[mo]) return qpow(query(l), cac(l+1,r,phi[mo])+phi[mo], mo);
        }
    }
    return qpow(query(l), last, mo);
}

int main() {
    phi[1]=1;
    for(ll i=2;i<M;i++) {
        if(!npri[i]) pri[p++]=i, phi[i]=i-1;
        for(int j=0;j<p && i*pri[j]<M;j++) {
            npri[i*pri[j]]=1;
            if(i%pri[j]==0) { phi[i*pri[j]]=phi[i]*pri[j]; break; }
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    int n, m;
    gn(n), gn(m);
    int c, l, r;
    ll x;
    for(int i=1;i<=n;i++) gn(x), updata(i, x), updata(i+1, -x);
    while(m--) {
        gn(c), gn(l), gn(r), gn(x);
        if(c==1) updata(l, x), updata(r+1, -x);
        else printf("%lld\n", cac(l, r, x));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3934.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆