题解 P3934 【[Ynoi2016]炸脖龙I】

考试考了这个题,出题人很良心没卡常给了\(9s\)但是本地测评空间炸了愉快的爆0,考场上脑子抽了死活觉得线段树维护区间求和行不通(,第一道自己做出来的\(Ynoi\),纪念一下

题目描述

维护一段区间,支持区间加,并求出一段区间的

\[a_{l}^{a_{l+1}^{a_{l+2}^{....a_{r}}}} \pmod p \]

解题思路

对于区间加,直接上线段树就可以,但是对于第二个操作求

\[a_{l}^{a_{l+1}^{a_{l+2}^{....a_{r}}}} \]

这东西貌似很抽象?而且指数部分还不能直接用欧拉定理模\(\varphi(p)\),因为指数上也是个递归的过程。

如果你做过P4139 上帝与集合的正确用法你就会觉得这柿子很眼熟,对的我们可以用拓展欧拉定理求啊

对于任意的正整数\(a\)和\(p\),且\(b\ge\varphi(p)\),有:

\[a^b\equiv a^{b\bmod\varphi(p)+\varphi(p)} \pmod p \]

而对于询问区间\([l,r] \pmod p\),我们设其询问结果记作\(s(l,r,p)\),我们可以推出:

\(s(l,r,p)=a_{l}^{s(l+1,r,p)\bmod\varphi(p)+\varphi(p)}\pmod p=a_{l}^{a_{l+1}^{s(l+2,r,p)\bmod\varphi(p)+\varphi(p)}}\pmod p=k\)

假设上式中出现的模\(p\)意义下的指数都大于等于\(\varphi(p)\)

将\(p\)不断地变成\(\varphi(p)\)需要\(O(log)\)次之后\(p\)变成\(1\)。而指数为1可以直接计算。对于询问\(s(l,r,p)\)可以递归做:

\((1)\)如果\(l=r\)或者\(p=1\)则直接反回\(a_{l}\)。

\((2)\)否则递归到\(s(l+1,r,\varphi(p))\),记其为\(tmp\)。如果\(tmp\ge\varphi(p)\)则返回 ,否则反回

那么我们现在的问题在于如何判断指数是否大于\(\varphi(p)\)

对于\(2^{2^{2^{2^2}}}\ge 2 \times 10^7\)

所以,我们只需要取出\([l+1,r]\)的前\(5\)个数,(如果\([l+1,r]\)的区间长度不足\(5\)则取区间\([l+1,r]\)内所有数,如果\([l+1,r]\)内第一个\(1\)出现的位置为\(x\)则取\([l+1,x-1]\)内所有数)

如果取出的数的个数为\(5\)则一定大于\(\varphi(p)\)。或者在前五个数内找到为\(1\)的,否则可以记录并直接往前暴力算然后判断即可

时间复杂度为\(O(p+nlognlogp)\)

最后注意大力卡常即可或者写常数更小的树状数组

#include<bits/stdc++.h>
    
#define LL long long
    
#define _ 0
    
#define R register

// #define AME__DEBUG
    
using namespace std;
    
// #define AME__

/*Grievous Lady*/
    
const int BUF_SIZE = 1 << 12;
    
char buf[BUF_SIZE] , *buf_s = buf , *buf_t = buf + 1;
    
#define PTR_NEXT() \
{ \
    buf_s ++; \
    if(buf_s == buf_t) \
    { \
        buf_s = buf; \
        buf_t = buf + fread(buf , 1 , BUF_SIZE , stdin); \
    } \
}
    
template <typename _m_> inline void mian(_m_ & _n_){
    LL _x_ = 0 , _nega_ = 0;
    while(*buf_s != '-' && !isdigit(*buf_s)) PTR_NEXT(); if(*buf_s == '-'){_nega_ = 1; PTR_NEXT();}
    while(isdigit(*buf_s)){_x_ = _x_ * 10 + *buf_s - '0'; PTR_NEXT();} if(_nega_) _x_ = -_x_; (_n_) = (_x_);
}

#define int long long

template <typename _n_> bool cmax(_n_ &a , const _n_ &b){ return a < b ? a = b , 1 : 0; }
    
template <typename _n_> bool cmin(_n_ &a , const _n_ &b){ return a > b ? a = b , 1 : 0; }

const int kato = 2e7 + 10;

const int atri = 2e7;

inline int quick_pow(int a , LL b , int mod){
    int res = 1;
    for(; b ; b >>= 1 , a = 1LL * a * a % mod){
        if(b & 1){
            res = 1LL * res * a % mod;
        }
    }
    return res;
}

LL n , m , cnt , opt , l , r , p , las[kato] , a[kato] , phi[kato] , prime[kato];

bool ispri[kato];

struct tree{
    protected:

        struct node{
            node *ch[2];
            int l , r;
            LL sum , tag;
            node(int l = 0 , int r = 0 , LL sum = 0 , LL tag = 0): l(l) , r(r) , sum(sum) , tag(tag){
                ch[0] = ch[1] = NULL;
            }
            inline int mid(){
                return (l + r) >> 1;
            }
            inline void up(){
                sum = ch[0] -> sum + ch[1] -> sum;
            }
            inline void add_val(LL v){
                tag += v , sum += 1LL * (r - l + 1) * v;
            }
            inline void down(){
                if(tag){
                    ch[0] -> add_val(tag) , ch[1] -> add_val(tag) , tag = 0;
                }
            }
        }*root;

        inline void build(node *&o , int l , int r){
            o = new node(l , r);
            if(l == r){
                mian(a[l]);
                o -> sum = a[l];
                return;
            }
            build(o -> ch[0] , l , o -> mid()); build(o -> ch[1] , o -> mid() + 1 , r);
            o -> up();
        }

        inline void Modify(node *o , int l , int r , int val){
            if(l <= o -> l && o -> r <= r){
                o -> add_val(val);
                return;
            }
            o -> down();
            if(l <= o -> mid()){
                Modify(o -> ch[0] , l , r , val);
            }
            if(r > o -> mid()){
                Modify(o -> ch[1] , l , r , val);
            }
            o -> up();
        }

        inline LL ask(node *o , int x){
            if(o -> l == o -> r){
                return o -> sum;
            }
            o -> down();
            if(x <= o -> mid()){
                return ask(o -> ch[0] , x);
            }
            if(x > o -> mid()){
                return ask(o -> ch[1] , x);
            }
        }

    public:

        inline void build(int n){
            build(root , 1 , n);
        }

        inline void Modify(LL l , LL r , LL val){
            Modify(root , l , r , val);
        }

        inline LL ask(int x){
            if(las[x] == m) return a[x];
            las[x] = m;
            return a[x] = ask(root , x);
        }
}yuni;

inline int phi_(int l , int r , int mod){
    if(yuni.ask(l) % mod == 0) return 0;
    if(mod == 1) return 1;
    if(l == r) return yuni.ask(l) % mod + (yuni.ask(l) >= mod) * mod;
    int pos = min(l + 5 , r);
    for(int i = l + 1;i <= pos;i ++){ 
        if(yuni.ask(i) == 1){
            pos = i; break;
        }
    }
    LL g = 0 , last = yuni.ask(pos);
    for(int i = pos - 1 ; i >= l + 1 ; i --){
        g = last , last = 1;
        for(; g --> 0 ;){
            last *= yuni.ask(i);
            if(last > phi[mod]) return quick_pow(yuni.ask(l) % mod , phi_(l + 1 , r , phi[mod]) + phi[mod] , mod);
        }
    }
    return quick_pow(yuni.ask(l) % mod , last , mod);
}

inline void pri(){
    for(R int i = 2;i <= atri;i ++){
        if(!ispri[i]){
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for(R int j = 1;j <= cnt && i * prime[j] <= atri;j ++){
            ispri[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

inline int Ame_(){
#ifdef AME__
    freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout);
#endif
    mian(n) , mian(m); memset(las , -1 , sizeof(las));
    pri();
    yuni.build(n);
    for(; m --> 0 ;){
        mian(opt) , mian(l) , mian(r) , mian(p);
        if(opt == 1) yuni.Modify(l , r , p);
        if(opt == 2) printf("%lld\n" , (phi_(l , r , p)) % p);
    }
    // fclose(stdin); fclose(stdout);
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
signed main(){;}
上一篇:洛谷 [P1220] 关路灯


下一篇:pl/sql oracle数据库中文数据显示异常或者不能使用中文查询的解决办法