题解 P3934 【Nephren Ruq Insania】

· · 题解

update：修正了题解代码。

zcy 神仙写的题解小蒟蒻表示看不太懂啊。。
而且做这题之前要做 相逢是问候？明明是这题更简单的样子。
好吧不扯了我们来说题解。

先考虑一下没有修改操作应该怎么搞，这题需要用到扩展欧拉定理：

a^b \equiv \begin{cases} a^b \ , \ (b < \varphi (p)) \\ a^{b \bmod \varphi(p) +\varphi(p)} \ , \ (b \geq \varphi(p)) \end{cases} \pmod p

此处的 \varphi(p) 就是数论中的欧拉函数。
然后我们就很高兴地写出了一个递归函数来求解： 

int solve(int l,int r,int p){
    if(p==1) return 0; //模数为1,结果必然为0
    if(l==r) return a[l]%p; //查询区间大小为1,直接返回即可
    return power(a[l],solve(l+1,r,phi(p))+phi(p),p); //phi(p)就是欧拉函数,递归求解
}

其中 power 函数输入 a,b,p，求 a^b\text{ mod }p。
随便试几组数据，就会发现这么做是有问题的。。
原因就在于我们没有判断 b 和 \varphi(p) 的大小关系，那怎么解决这个问题呢？

这里我用了一种粗暴的方法：
用一个 struct 来存答案，内含两个属性：一个是运算结果，一个是这个值是否大于 \varphi(p)。
具体写起来是这个样子的： 

struct node{
    int val;
    bool flag;
    node(int val=0,bool flag=false):val(val),flag(flag){}
};

于是我们把之前的递归函数改进成这样： 

node solve(int l,int r,int p){
    node res;
    if(p==1) return node(0,true); 
    if(a[l]==1) return node(1,false);
    if(l==r) return a[l]<p?node(a[l],false):node(a[l]%p,true); //上面说的特判,如果a[l]>=p就需要返回true
    res = solve(l+1,r,phi(p));
    if(res.flag) res.val += phi(p); //根据下一层递归的返回值,判断指数是否应该多加上p
    return power(a[l],res.val,p);
}

此处的 power 函数也是 node 类型的，里面会判断 a^b 是否大于 p。
至于这里为什么是和 p 而不是和 \varphi(p) 比较，因为这里的 p 对于上一层递归来说，就是 \varphi(p) 了。

现在已经把不带修改的部分完成了！
带上修改其实也很好做。直接写一个树状数组，区间加的时候就直接加， solve 函数中把 a_l 改为树状数组查询第 l 项。

总结：思路很简单，代码很难写。于是这道大毒瘤题就被我们做完了。

最后补充一下时间复杂度的证明：

对于任意大于 2 的整数 n，\varphi(n) 都为偶数。而对于偶数 n，显然有 \varphi(n)\le n/2。
所以对一个数取 \mathcal O(\log n) 次欧拉函数，就会变为 1。

也就是 \varphi(p),\varphi(\varphi(p)),\varphi(\varphi(\varphi(p))) \cdots 这么算下去，\mathcal O(\log p) 次后会得到 1。
所以那个递归函数最多会进行 \mathcal O(\log p) 层。
对于每一层，都会进行一次 \mathcal O(\log n) 的树状数组查询，和 \mathcal O(\log p) 的快速幂。
此外还有 \Theta(p) 的预处理，计算 [1,p] 所有数的欧拉函数。 所以总时间复杂度就是 \mathcal O(p+q\log np \log p)。

献上巨丑无比的代码： 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<bitset>
#define N 500003
#define M 20000003
#define inf 0x3f3f3f3f
#define int long long
using namespace std;

struct node{
    int rs;
    bool flag;
    node(int rs=0,bool flag=false):rs(rs),flag(flag){}
};

int a[N],phi[M],pr[M];
int n,q;
bitset<M> vis;

inline void read(int &x);
void print(int x);
inline node power(int a,int t,int p);
void init();
node solve(int l,int r,int p);
inline void add(int l,int r,int x);
inline void qwq(int i,int x);
inline int query(int i);
inline int lowbit(int x);

signed main(){
    init();
    int l,r,op,x,t;
    node ans;
    read(n),read(q);
    for(int i=1;i<=n;++i){
        read(t);
        add(i,i,t);
    }
    while(q--){
        read(op),read(l),read(r),read(x);
        if(op==1) add(l,r,x);
        else{
            ans = solve(l,r,x);
            print(ans.rs);
            putchar('\n');
        }
    }
}

node solve(int l,int r,int p){
    int ph,al = query(l);
    node res;
    if(p==1) return node(0,1);
    if(al==1) return node(1,0);
    if(l==r) return al<p?node(al,0):node(al%p,1);
    ph = phi[p];
    res = solve(l+1,r,ph);
    if(res.flag) res.rs += ph;
    return power(al,res.rs,p);
}

inline void init(){
    int cnt = 0;
    phi[1] = 1;
    for(register int i=2;i<=20000000;++i){
        if(!vis[i]){
            pr[++cnt] = i;
            phi[i] = i-1;
        }
        for(register int j=1;j<=cnt;++j){
            int t = i*pr[j];
            if(t>20000000) break;
            vis[t] = 1;
            if(i%pr[j]==0){
                phi[t] = phi[i]*pr[j];
                break;
            }
            phi[t] = phi[i]*(pr[j]-1);
        }
    }
}

inline node power(int a,int t,int p){ // 做快速幂时，判断答案是否大于等于 p 
    node res = node(1,0);
    if(a>=p){
        a %= p;
        res.flag = 1;
    }
    while(1){
        if(t&1) res.rs = res.rs*a;
        if(res.rs>=p){ 
            res.flag = 1;
            res.rs %= p;
        }
        t >>= 1;
        if(t==0) break;
        a = a*a;
        if(a>=p){
            res.flag = 1;
            a %= p;
        }
    }
    return res;
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline void add(int l,int r,int x){
    qwq(l,x);
    qwq(r+1,-x);
}

inline void qwq(int i,int x){
    while(i<=n){
        a[i] += x;
        i += lowbit(i);
    }
}

inline int query(int i){
    int res = 0;
    while(i){
        res += a[i];
        i -= lowbit(i);
    }
    return res;
}

inline int lowbit(int x){
    return x&(-x);
}