洛谷P4691 Nephren Ruq Insania 题解

本题和 P3934 [Ynoi2016] 炸脖龙 I 完全一致。

题目链接：P4691 Nephren Ruq Insania（本题没有数据，需要在 P3934 提交）

题意：

奈芙莲·卢可·印萨尼亚 (Nephren-Ruq-Insania)

威廉想要救下奈芙莲，但是他自己也已经处于崩溃的边缘。

冥冥之中他想起了曾经学习过的一种魔法。在这最后一刻，或许已经是唯一的办法了。

这种魔法操作的对象是一个咒语组成的序列，每一个单独的咒语拥有自己的法力值。

威廉需要不断地按照之前的记忆，对某一段区间的法力值加上一个数，或者求出某一段区间的法咒共鸣。

法咒共鸣具体而言是这么计算的：

对于区间 $[l,r]$ ， 查询

$$\mathrm{pow}(a_l,\,\mathrm{pow}(a_{l+1},\,\mathrm{pow}(a_{l+1},\,\cdots))) \bmod p$$

一直到 $\mathrm{pow}(a_r,\,1)$ 。其中 $\mathrm{pow}(a,b)$ 表示 $a^b$ 。

请注意每次的模数不同。

时间不够了，威廉自己无力计算这么复杂的魔法。但是这是最后的希望了。

能否拯救奈芙莲，就靠您了。

输入格式：

第一行两个整数 $n,m$ ，表示序列长度和操作数。

接下来一行，$n$ 个整数 $a_i$ 表示这个序列。

接下来 $m$ 行，可能是以下两种操作之一：

• 1 l r x ，表示区间 $[l,r]$ 加上 $x$ 。

• 2 l r p ，表示进行一次法咒共鸣，模数为 $p$ 。

输出格式：

对于每个操作 2，输出一行表示答案。

数据范围：

$1\le n , m \le 5\times 10^5$ ，序列中每个数在 $[1,2\times 10^9]$ 内。

$1\le p \le 2 \times 10^7$, 每次加上的数在 $[0,2\times 10^9]$ 内。

听说这个数据结构叫奈芙莲树，难评。

这道题主要利用的就是 $\mathcal{O}(\varphi^{*}(x)=1) = \mathcal{O}(\log x)$ ，参考 P3747 相逢是问候

另外防止大家不理解，贴一下扩展欧拉定理

$$\begin{aligned} a^b \equiv \begin{cases} a^b,&b< \varphi(p)\\\\ a^{b \ \bmod \ \varphi(p)+\varphi(p)},&b\ge \varphi(p) \end{cases} \pmod{p} \end{aligned}$$

不过这道题底数不固定，没法光速幂预处理。

如果直接递归 $\mathrm{pow}$ 的话，我们没法判断 $b$ 是否小于 $\varphi(p)$ 。

不过注意到

$$\mathrm{pow}(2, \mathrm{pow}(2, \mathrm{pow}(2, \mathrm{pow}(2, \mathrm{pow}(2, 1))))) = 2^{2^{2^{2^2}}} > 2\times 10^7$$

也就是说，我们可以暴力算 $4$ 次 $\mathrm{pow}$ ，如果这个值小于 $\varphi(p)$ ，就返回 $\mathrm{pow}(a_l,b)$ ，否则递归。

说了半天，区间加法怎么办呢？我们可以用树状数组维护差分数组的方式来实现。

不过注意到如果每次都要查树状数组会有很大的常数，我们可以用类似于记忆化的方式存下当前的值。

时间复杂度 $\mathcal{O}(n \log n \log p)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))
#define M ((int)(2e7 + 15))

char ck[M];
int n, id, pcnt, pri[M / 10], phi[M]; ll tr[N];
int qpow(ll a, ll b, int p)
{
    ll r = 1;
    for(a %= p; b; b >>= 1, a = a * a % p)
        if(b & 1) r = r * a % p;
    return r;
}
int lowbit(int x) { return x & (-x); }
void add(int x, ll v) { ++id; for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
ll qry(int x, ll r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
void Euler(int _ = M - 5)
{
    phi[1] = 1; int *p = pri;
    for(int i = 2; i <= _; i++)
    {
        if(!ck[i]) { p[++pcnt] = i, phi[i] = i - 1; }
        for(int j = 1; j <= pcnt && p[j] * i <= _; j++)
        {
            const int pos = p[j] * i; ck[pos] = true;
            if(i % p[j]) { phi[pos] = phi[i] * phi[p[j]]; }
            else { phi[pos] = phi[i] * p[j]; break; }
        }
    }
}
struct Arr
{
    ll v[N]; int w[N];
    ll& operator[](int x)
    { 
        if(w[x] == id) return v[x];
        w[x] = id; v[x] = qry(x); return v[x];
    }
} a;
void update(int l, int r, int x) { add(l, x); add(r + 1, -x); }
ll solve(int l, int r, int p)
{
    if(a[l] % p == 0) return 0;
    if(l == r) return a[l] % p + (a[l] >= p ? p : 0);
    int k = min(l + 5, r);
    for(int i = l + 1; i <= k; i++) if(a[i] == 1) { k = i; break; }
    ll t = 0, b = a[k];
    for(int i = k - 1; i > l; i--)
        for(t = b, b = 1; t--; ) {
            b *= a[i]; if(b > phi[p]) return qpow(a[l], solve(l + 1, r, phi[p]) + phi[p], p);
        }
    return qpow(a[l], b, p);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q; id = 0; Euler();
    for(int i = 1; i <= n; i++) { cin >> a[i], add(i, a[i] - a[i - 1]); }
    for(int i = 1, op, l, r, x; i <= q; i++)
    {
        cin >> op >> l >> r >> x;
        if(op == 1) update(l, r, x);
        else cout << (x == 1 ? 0 : solve(l, r, x) % x) << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/vu9gjdd8

---

题外话：

下面是题目背景，稍微修了一下格式。

奈芙莲·卢可·印萨尼亚(Nephren-Ruq-Insania)

同为妖精仓库的成体妖精兵，天赋不如珂朵莉一般，只是一个平凡的妖精。

睡觉时如同毯子一般在威廉身上为其保暖。

习惯于粘着威廉，在梦境中与艾尔梅莉亚交谈时，自称就像是威廉的宠物一样。

她只是一个非常普通的黄金妖精。

在援救打捞队的作战中，他们不幸与（几乎是所有的）第六兽相遇了。

此时的珂朵莉因为接触到星神艾露可本体，正处于昏迷之中。而威廉也无法离开珂朵莉。

默默守护在房间外的她，提起圣剑，走向了战场。

作为本身天赋只是一般的妖精少女，她难以对抗无数倍于自己的六号兽。

没有多久，她开始体力不支。

终于，在源源不断的六号兽面前，她难以抵挡了……

终于，由于魔力过度激发，她已经处在了魔力失控的边缘……

“威廉，拯救，是我们黄金妖精的使命。”

“况且，威廉之前已经救过我们了。”

“所以，已经没有问题了。”