P3934题炸脖龙I，如何巧妙解决？
摘要：P3934 [Ynoi Easy Round 2016] 炸脖龙 I 大意 区间加，求 (a[l]^{a[l+1]^{a[l+2]^{dots ^{a[r]}}}} mod p) 的值。 思路 对
P3934 [Ynoi Easy Round 2016] 炸脖龙 I
大意
区间加，求 \(a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p\) 的值。
思路
对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 \(p\) 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？
\(\varphi(n)\) 就表示小于等于 \(n\) 与 \(n\) 互质的数的个数，\(\varphi(1) = 1, \varphi(p) = p - 1\)，这里的 \(p\) 是质数。那么 \(\phi(n)\) 应该怎么算呢？我们由素数分解定理，就可以有这样的公式：
\[n \prod_{p | n} (1 - \frac{1}{p})
\]
这个过程我们是可以用线性筛预处理这个 \(\varphi(n)\) 的。
好的，预处理讲完了，接下来讲欧拉定理，当 \(\gcd(a, m) = 1\)，那么 \(a ^ {\varphi(m)} \equiv 1 \pmod m\)，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下：
\[a ^ b \equiv
\begin{cases}
a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1
\\
a ^ b & \gcd(a, m) \neq 1, b < \varphi(m)
\\
a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m)
\end{cases} \pmod{m}
\]
好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 \(\varphi\) 显然最后会变成 \(1\)，那么要取多少次呢？我们想想对于 \(\varphi(2 ^ k)\) 来说，其等于 \(2 ^ {k - 1}\)，对于质数是 \(p - 1\)，其如果是质数就减去一变成偶数，然后就会很快变小。
那么我们这个题直接写递归的话，递归层数最多就是 \(\log\) 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 \(1\)，注意快速幂的地方，也要改一下。
代码
#include<iostream>
using namespace std;
#define int long long
const int MAXN = 2 * 1e7 + 5;
int a[MAXN], n, m;
int pri[MAXN], phi[MAXN], tot = 0;
int sum[MAXN];
bool vis[MAXN];
void init(){
phi[1] = 1;
for(int i = 2;i < MAXN;i ++){
if(!vis[i]){
phi[i] = i - 1;
pri[++ tot] = i;
}
for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
// for(int i = 1;i < 5;i ++){
// cout << phi[i] << ' ';
// }
}
int lowbit(int x){
return x & -x;
}
void add(int x, int k){
while(x <= n){
sum[x] += k;
x += lowbit(x);
}
}
int ask(int x){
int res = 0;
while(x){
res += sum[x];
x -= lowbit(x);
}
return res;
}
int qpow(int a, int b, int p){
int res = 1;
bool flag = 0;
if(a >= p){
flag = 1;
a %= p;
}
while(b){
if(b & 1) res = res * a;
if(res >= p){
res %= p;
flag = 1;
}
a = a * a;
if(a >= p){
a %= p;
flag = 1;
}
b >>= 1;
}
return flag ? res + p : res;
}
int solve(int l, int r, int p){
int val = a[l] + ask(l);
if(p == 1) return 1;
if(l == r){
if(val >= p) return val % p + p;
else return val;
}
int cnt = solve(l + 1, r, phi[p]);
return qpow(val, cnt, p);
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
init();
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i <= m;i ++){
int op, l, r, x;
cin >> op >> l >> r >> x;
if(op == 1) add(l, x), add(r + 1, -x);
else cout << solve(l, r, x) % x << '\n';
}
return 0;
}