题意
给出一个模(p)（(p)是素数）意义下的序列，支持两种操作：
- 区间乘一个数；
- 询问一个区间的元素构成的群的大小。
保证序列中的数时时刻刻不为(0)。
题解
一道好题……sb了好久。
第一个想法显然是先找到一个原根(g)，再取指标进行运算。
然后对于一个区间(g ^ {k_l}, g ^ {k_{l + 1}}, ldots, g ^ {k_r})，生成群的生成元(omega)为(g ^ {(gcd{k_l, k_{l + 1}, ldots, k_r, p - 1})})，则群的大小为(frac{p - 1}{ind_g(omega)})。
看这个(gcd)，因为要区间修改，所以要维护原序列和原序列的差分两个数组，因为
这样便把区间修改变成单点修改。
复杂度是(mathcal O((n + q) sqrt {(n + q) p} + q log ^ 2 n))，因为要bsgs求指标（我tmbsgs块大小还写挂了）。
然而这样是过不了的。那咋整啊？
XZA说指标的信息有冗余，实际上只需要求阶即可（求阶是(mathcal O(log ^ 2 p))的）。然而当时并没有理解这句话的意思，尽管感性理解好像是这回事。
考虑直接用阶做。
假设我们已经知道了区间([l, r])中每个元素的阶，那么如何求其生成群的大小？考虑两两合并。
对于一个阶为(a)的元素和一个阶为(b)的元素，其生成的群可分别表示为(<g ^ {frac{p - 1}{a}}>, <g ^ {frac{p - 1}{b}}>)。
那么合并之后，群可表示为(<g ^ {gcd{(frac{p - 1}{a}}, frac{p - 1}{b})}>)。则新的群的大小为(frac{p - 1}{gcd{(frac{p - 1}{a}}, frac{p - 1}{b})})。
（这其中用到了一个很基础的定理：循环群的大小等于其生成元的阶。）
简单运算一下，发现合并后群的大小就等于( ext{lcm} (a, b))。所以，这要求维护一个区间( ext{lcm})。但是区间( ext{lcm})也许并没有带区间乘的优秀做法。
实际上，我们可以维护一个商分，即(a_i' = a_i * {a_{i - 1}} ^ {-1})。这样区间乘就变成了单点乘。
根据这题的询问是群，则((a_l, a_{l + 1} * {a_l} ^ {-1}, ldots, a_r * {a_{r - 1}} ^ {-1}))形成的群和((a_l, a_{l + 1}, ldots, a_r))形成的群并没有区别，所以维护商分完全可行。
因此，大概只需要一棵线段树维护原序列，一棵线段树维护商分序列的每个元素的阶的区间( ext{lcm})即可。
复杂度(mathcal O((n + q) log ^ 2 n))。常数极大。（以上(log n)和(log p)混用了，明白就好）
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pii;
const int N = 1e5 + 5;
int mod, _mod, n, q;
int a[N], g[N << 2], v[N << 2];
vector <pii> pf;
int lcm (int x, int y) {
return x / __gcd(x, y) * y;
}
int power (int x, int y, int mod) {
int ret = 1;
for ( ; y; y >>= 1, x = 1ll * x * x % mod) {
if (y & 1) {
ret = 1ll * ret * x % mod;
}
}
return ret;
}
void factorize (int x) {
pf.clear();
int t = sqrt(x + 1);
for (int i = 2, c; i <= t; ++i) {
if (x % i == 0) {
c = 0;
for ( ; x % i == 0; x /= i, ++c);
pf.push_back(make_pair(i, c));
}
}
if (x > 1) {
pf.push_back(make_pair(x, 1));
}
}
int ord (int x) {
int ret = _mod;
for (auto q : pf) {
for (int i = 1; i <= q.se; ++i) {
if (power(x, ret / q.fi, mod) == 1) {
ret /= q.fi;
} else {
break;
}
}
}
return ret;
}
void build (int o, int l, int r) {
v[o] = 1;
if (l == r) {
g[o] = v[o] = a[l];
if (l) {
g[o] = 1ll * g[o] * power(a[l - 1], mod - 2, mod) % mod;
}
g[o] = ord(g[o]);
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
g[o] = lcm(g[o << 1], g[o << 1 | 1]);
}
void pushdown (int o) {
if (v[o] != 1) {
v[o << 1] = (1ll * v[o << 1] * v[o]) % mod;
v[o << 1 | 1] = (1ll * v[o << 1 | 1] * v[o]) % mod;
v[o] = 1;
}
}
int query (int o, int l, int r, int x) {
if (l == r) {
return v[o];
}
pushdown(o);
int mid = (l + r) >> 1;
if (x <= mid) {
return query(o << 1, l, mid, x);
} else {
return query(o << 1 | 1, mid + 1, r, x);
}
}
void modify (int o, int l, int r, int x, int v) {
if (l == r) {
g[o] = 1ll * query(1, 1, n, l) * power(query(1, 1, n, l - 1), mod - 2, mod) % mod;
g[o] = ord(g[o]);
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
modify(o << 1, l, mid, x, v);
} else {
modify(o << 1 | 1, mid + 1, r, x, v);
}
g[o] = lcm(g[o << 1], g[o << 1 | 1]);
}
void modify (int o, int l, int r, int x, int y, int z) {
if (x <= l && r <= y) {
v[o] = 1ll * v[o] * z % mod;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (x <= mid) {
modify(o << 1, l, mid, x, y, z);
}
if (y > mid) {
modify(o << 1 | 1, mid + 1, r, x, y, z);
}
}
int query (int o, int l, int r, int x, int y) {
if (x <= l && r <= y) {
return g[o];
}
int mid = (l + r) >> 1, ret = 1;
if (x <= mid) {
ret = lcm(ret, query(o << 1, l, mid, x, y));
}
if (y > mid) {
ret = lcm(ret, query(o << 1 | 1, mid + 1, r, x, y));
}
return ret;
}
int read () {
int x = 0; char ch = getchar();
for ( ; !isdigit(ch); ch = getchar());
for ( ; isdigit(ch); ch = getchar()) {
x = x * 10 + ch - '0';
}
return x;
}
void write (int x) {
if (x >= 10) {
write(x / 10);
}
putchar('0' + x % 10);
}
int main () {
mod = read(), n = read(), q = read();
factorize(_mod = mod - 1);
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
build(1, 1, n);
for (int i = 1, o, l, r, x; i <= q; ++i) {
o = read(), l = read(), r = read();
if (o == 1) {
x = read();
modify(1, 1, n, l, r, x);
modify(1, 1, n, l, x);
if (r < n) {
modify(1, 1, n, r + 1, -x);
}
} else {
x = ord(query(1, 1, n, l));
if (l < r) {
x = lcm(x, query(1, 1, n, l + 1, r));
}
write(x), putchar('
');
}
}
return 0;
}