P3934 [Ynoi2016]炸脖龙I
题目链接
树状数组 + 扩展欧拉定理。
对于修改，直接树状数组差分。
对于询问，我们设(s(l, r, p))代表区间([l, r])的询问。所以递归下去就可以做(s(l, r, p) = a[l]^{s(l + 1, r, phi(p) + phi(p))} mod p)（假设(s(l, r, p))都大于(phi(p))），这是扩展欧拉定理。
对于phi我们直接预处理出([1,2e7])的就好了。然后分情况：
只要存在一个(i <= r，a[i] = 1)，那么(s(l, r, p) = s(l, i, p))，因为1的任何次方都是1。
对于一个区间，如果这个区间的长度大于5，并且没有一个1，那么它肯定可以往下递归，因为它肯定大于(p)：(2 ^ {2 ^ {2 ^ {2 ^ 2}}} = 2^{65536} > 2e7 = p)。
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 5e5 + 5, M = 2e7 + 5;
int n, m, cnt;
int prime[M], is_prime[M], phi[M];
long long a[N], t[N];
void make_phi() {
phi[1] = 1;
for(int i = 2;i <= M - 5; i++) {
if(!is_prime[i]) prime[++cnt] = i, phi[i] = i - 1;
for(int j = 1;j <= cnt && i * prime[j] <= M - 5; j++) {
is_prime[i * prime[j]] = 1;
if(!(i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
long long ksm(long long x, long long y, long long mod) {
long long res = 1; x %= mod; // 一定要加这一句！！！！！
while(y) {
if(y & 1) res = 1ll * x * res % mod;
x = 1ll * x * x % mod; y >>= 1;
}
return res % mod;
}
int lowbit(int x) { return x & -x; }
void change(int x, long long val) { for(; x <= N - 5; x += lowbit(x)) t[x] += val; }
long long ask(int x) {
long long res = 0; for(; x ; x -= lowbit(x)) res += t[x]; return res; }
long long query(int l, int r, int p) {
if(ask(l) % p == 0) return 0;
else if(p == 1) return 1;
else if(l == r) return ask(l) % p + (ask(l) >= p ? p : 0);
int rs = min(r, l + 5);
for(int i = l + 1;i <= rs; i++) if(ask(i) == 1) { rs = i; break; }
long long la = ask(rs);
for(int i = rs - 1;i >= l + 1; i--) {
long long tmp = la, now = ask(i); la = 1;
while(tmp --> 0) {
la *= now;
if(la > phi[p]) {
return ksm(ask(l), query(l + 1, r, phi[p]) + phi[p], p);
}
}
}
return ksm(ask(l), la, p);
}
int main() {
n = read(); m = read(); make_phi();
// for(int i = 1;i <= 10; i++) cout << i << " " << phi[i] << endl;
for(int i = 1;i <= n; i++) a[i] = read(), change(i, a[i] - a[i - 1]);
for(int i = 1, opt, l, r;i <= m; i++) {
opt = read(); l = read(); r = read();
long long x = read();
if(opt == 1) change(l, x), change(r + 1, -x);
if(opt == 2) printf("%lld
", query(l, r, x) % x);
}
fclose(stdin); fclose(stdout);
return 0;
}