Luogu

分析

这种题显然要用扩展欧拉定理

$$ a^b\bmod p=\begin{cases}a^b\bmod p,&b<\varphi(p)\\a^{b\bmod\varphi(p)+\varphi(p)}\bmod p,&b\geq \varphi(p)\end{cases} $$

先考虑没有修改的情况,我们只需要像其它扩展欧拉定理题一样递归下去即可。显然只会递归 $\mathcal{O}(\log p)$ 层,所以复杂度是对的。

现在考虑这个修改。我们实际上只需要知道每个位置的值,因此用树状数组实现区间修改、单点查询即可。

$\varphi(p)$ 的值显然不能在递归时 $\mathcal{O}(\sqrt{p})$ 求,但是 $p$ 比较小,可以线性筛预处理。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define int long long
using namespace std;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10,L=20000000+10;

int n,m;

int p[L],v[L],phi[L],cnt=0;
void sieve(int n) {
    phi[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,phi[i]=i-1;
        for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
            else { phi[i*p[j]]=phi[i]*p[j]; break; }
        }
    }
}

int c[N];
void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

pair<int,int> qpow(int a,int b,int mod) {
    pair<int,int> c(1,0);
    if (a>=mod) a%=mod,c.second=1;
    for (;b;b>>=1) {
        if (b&1) c.first*=a;
        if (c.first>=mod) c.first%=mod,c.second=1;
        a*=a;
        if (a>=mod) a%=mod,c.second=1;
    }
    return c;
}
pair<int,int> calc(int p,int lim,int mod) {
    int a=sum(p);
    if (mod==1) return make_pair(0,1);
    if (a==1) return make_pair(1,0);
    if (p==lim) return make_pair(a%mod,a>=mod);
    pair<int,int> nxt=calc(p+1,lim,phi[mod]);
    return qpow(a,nxt.first+nxt.second*phi[mod],mod);
}

signed main() {
    sieve(20000000);
    n=read(),m=read();
    for (int i=1,w;i<=n;++i) w=read(),add(i,w),add(i+1,-w);
    while (m--) {
        int op=read(),l=read(),r=read(),w=read();
        if (op==1) add(l,w),add(r+1,-w);
        else printf("%lld\n",calc(l,r,w).first);
    }
    return 0;
}
最后修改:2020 年 06 月 17 日 04 : 22 PM