不算很难的一道题
原题的数据虽然很小，但是我们不能欺负它，我们就要当$S[i] \leqslant 10^9$来做这题
最小公倍数 = 所有的质因数取可能的最大幂相乘
对于$> \sqrt S$的质数，幂只会为$0$或者$1$，只要维护有没有存在即可
对于$< \sqrt S$的质数，在$S[i] \leqslant 50000$时，我们可以暴力对每个质数维护相应地幂次
但是在$S[i] \leqslant 10^9$时，我们考虑把$p, p^2, p^3, ....$单独看做一种质数，每种质数都有$p$的贡献来维护
由于删除操作不好做，因此考虑离线扫描线做到只有插入
左端点从右到左扫，只要维护右端点的答案即可
可以发现，每种质数出现的区间一定是一段后缀，因此可以考虑维护后缀积来快速回答
每次扫描线加入点时，只要分解这个点，然后把相应地质数的后缀积改变即可
如果$S[i] \leqslant 50000$，那么复杂度可以做到$O(n \log^2 n + q \log n)$
否则，复杂度可以做到$O(n v(n) + n \log^2 n + q \log n)$，其中$v(n)$为分解$n$的复杂度
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; extern inline char gc() {
static char RR[], *S = RR + , *T = RR + ;
if(S == T) fread(RR, , , stdin), S = RR;
return *S ++;
}
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
} #define ri register int
#define sid 50005
const int mod = ; int n, Q;
int v[sid], ans[sid];
struct Ask {
int l, r, id;
friend bool operator < (Ask a, Ask b)
{ return a.l > b.l; }
} q[sid]; int inv[sid], pre[sid];
int nop[sid], pr[sid], mp[sid], tot;
void Sieve() {
for(ri i = ; i <= ; i ++) {
if(!nop[i]) pr[++ tot] = i, mp[i] = i;
for(ri j = ; j <= tot; j ++) {
int p = i * pr[j]; if(p > ) break;
nop[p] = ; mp[p] = pr[j];
if(i % pr[j] == ) break;
}
}
inv[] = ;
for(ri i = ; i <= ; i ++)
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
} int val[sid << ]; #define ls (o << 1)
#define rs (o << 1 | 1)
inline void inh(int o) { val[o] = 1ll * val[ls] * val[rs] % mod; } void build(int o, int l, int r) {
val[o] = ; if(l == r) return;
int mid = (l + r) >> ;
build(ls, l, mid); build(rs, mid + , r);
} void upd(int o, int l, int r, int p, int v, int opt) {
if(l == r) {
if(opt == ) val[o] = 1ll * val[o] * v % mod;
else val[o] = 1ll * val[o] * inv[v] % mod;
return;
}
int mid = (l + r) >> ;
if(p <= mid) upd(ls, l, mid, p, v, opt);
else upd(rs, mid + , r, p, v, opt);
inh(o);
} int qry(int o, int l, int r, int ml, int mr) {
if(ml > r || mr < l) return ;
if(ml <= l && mr >= r) return val[o];
int mid = (l + r) >> ;
return 1ll * qry(ls, l, mid, ml, mr) * qry(rs, mid + , r, ml, mr) % mod;
} void solve(int v, int c, int now) {
if(!v) return; int w = ;
for(ri i = ; i <= c; i ++) {
w = w * v;
if(pre[w]) upd(, , n, pre[w], v, -);
upd(, , n, now, v, ); pre[w] = now;
}
} void add(int o) {
int w = v[o], lstp = , cnt = ;
while() {
if(mp[w] != lstp)
solve(lstp, cnt, o), lstp = mp[w], cnt = ;
else cnt ++;
if(w == ) break; w /= mp[w];
}
} int main() { n = read(); Q = read(); Sieve();
for(ri i = ; i <= n; i ++) v[i] = read(); for(ri i = ; i <= Q; i ++)
q[i].id = i, q[i].l = read(), q[i].r = read();
sort(q + , q + Q + ); build(, , n);
for(ri i = n, j = ; i >= ; i --) {
add(i);
while(q[j].l == i && j <= Q)
ans[q[j].id] = qry(, , n, i, q[j].r), j ++;
} for(ri i = ; i <= Q; i ++) printf("%d\n", ans[i]);
return ;
}