早年数论题。
题目链接
给定一个长为 的正整数序列 （1-index），维护两种操作（共 次）：
- 给定 ，对于所有 ，令 ；
- 给定 ，求 ，其中
首先熟知欧拉降幂公式（扩展欧拉定理）：
对于第一种情况， 是否互质有时不好讨论，幸好可以直接应用不互质的版本，即
直接应用扩展欧拉定理，我们有
其中 是 Iverson bracket。
在递归的过程中维护条件是否成立即可。
那么，如此计算的复杂度是什么呢？
首先考虑一个剪枝，若 ，则显然可以直接终止递归过程。
容易证明，从 开始，不断这个数取欧拉函数，最多取 次，就可以把这个数变成 。
因此递归最多进行 层。
维护区间加是容易的，使用一个差分树状数组，容易做到 区间加， 单点查值。
总的来讲，操作 1 的单次复杂度为 ；操作 2 的单次复杂度为 。
最开始需要 预处理 的欧拉函数值。
初始化树状数组可以做到 ，但是我懒得写了。
总复杂度 。
需要特判掉 的情况，由于数组恒正，因此指数取模前是大于 的，故计算时应该取 。
#include <bits/stdc++.h>
using namespace std;
template <uint32_t L> struct Jabberwocky {
bitset<L> not_prime;
array<uint32_t, L> phi;
vector<uint64_t> fenwick;
Jabberwocky() {
vector<uint32_t> primes;
primes.reserve(L >> 1);
not_prime[0] = not_prime[1] = true;
for (uint32_t i = 2; i < L; ++i) {
if (!not_prime[i])
primes.push_back(i), phi[i] = i - 1;
for (uint32_t j : primes) {
if (i * j >= L)
break;
not_prime[i * j] = true;
if (i % j == 0) {
phi[i * j] = phi[i] * j;
break;
}
phi[i * j] = phi[i] * (j - 1);
}
}
}
void resize(size_t n) { fenwick.resize(n + 1); }
void suffer_add(size_t p, uint64_t x) {
for (; p < fenwick.size(); p += p & -p)
fenwick[p] += x;
}
void range_add(size_t l, size_t r, uint64_t x) {
suffer_add(l, x), suffer_add(r + 1, -x);
}
uint64_t get_point(size_t p) const {
uint64_t ret = 0;
for (; p; p -= p & -p)
ret += fenwick[p];
return ret;
}
static void reduce(uint64_t &value, uint32_t mod, bool &mark) {
if (value >= mod)
value %= mod, mark = true;
}
static pair<uint64_t, bool> fast_pow(uint64_t base, uint64_t exp,
uint32_t mod) {
bool mark = false;
uint64_t ret = 1;
for (reduce(base, mod, mark); exp;
exp >>= 1, base *= base, reduce(base, mod, mark))
if (exp & 1)
ret *= base, reduce(ret, mod, mark);
return make_pair(ret, mark);
}
pair<uint64_t, bool> range_query(size_t l, size_t r, uint32_t p) const {
if (p == 1)
return make_pair(static_cast<uint64_t>(0), false);
if (l == r)
return make_pair(get_point(l), false);
uint64_t base = get_point(l);
if (base < 2)
return make_pair(base, false);
if (base % p < 2)
return make_pair(base % p, true);
auto [exp, mark] = range_query(l + 1, r, phi[p]);
return fast_pow(base, mark ? exp + phi[p] : exp, p);
}
};
static constexpr uint32_t L = 20000003;
static Jabberwocky<L> jabberwocky;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
size_t n, q;
cin >> n >> q;
jabberwocky.resize(n);
for (size_t i = 1; i <= n; ++i) {
uint64_t x;
cin >> x;
jabberwocky.range_add(i, i, x);
}
while (q--) {
uint32_t op;
cin >> op;
switch (op) {
case 1: {
size_t l, r;
uint64_t x;
cin >> l >> r >> x;
jabberwocky.range_add(l, r, x);
break;
}
case 2: {
size_t l, r;
uint32_t p;
cin >> l >> r >> p;
cout << jabberwocky.range_query(l, r, p).first % p << endl;
break;
}
}
}
return 0;
}