题面
首先明确一点:我们只要求出区间乘积中每个质因数的指数即可
一个不难想到的暴力1:
对每个数分解质因数，然后莫队维护即可
$O(n\sqrt{nk})$(k为单个数的最大不同质因子个数)
一个不难想到的暴力2:
对每个质因子搞一个前缀和，然后暴力查即可
$O((n+m)\sum k)$
组合一下
设个阈值x
对小于x的质数用前缀和
对大于x的质数用莫队
发现x为1000时，小于x的质数168个
妥妥的
记得逆元预处理1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std;
const int mod = 19260817, radio = 1000, _max = 168;
int prime[10010], np[40010], cnt;
int n, m, sum[100010][200];
int p1[100010], p2[100010], b[200010], sze;
int a[100010];
int inv[mod + 10];
int buc[200010], nowl = 1, nowr, nowans = 1;
struct query {
int l, r, id;
} q[100010];
int qid[100010], qsize;
int ans[100010];
inline int cmp(const query &a, const query &b) {
return qid[a.l] == qid[b.l] ? qid[a.l] & 1 ? a.r < b.r : a.r > b.r : a.l < b.l;
}
inline void add(int x) {
if(p1[x]) {
nowans = 1ll * nowans * inv[buc[p1[x]]] % mod;
buc[p1[x]]++;
nowans = 1ll * nowans * buc[p1[x]] % mod;
}
if(p2[x]) {
nowans = 1ll * nowans * inv[buc[p2[x]]] % mod;
buc[p2[x]]++;
nowans = 1ll * nowans * buc[p2[x]] % mod;
}
}
inline void del(int x) {
if(p1[x]) {
nowans = 1ll * nowans * inv[buc[p1[x]]] % mod;
buc[p1[x]]--;
nowans = 1ll * nowans * buc[p1[x]] % mod;
}
if(p2[x]) {
nowans = 1ll * nowans * inv[buc[p2[x]]] % mod;
buc[p2[x]]--;
nowans = 1ll * nowans * buc[p2[x]] % mod;
}
}
int main() {
np[1] = inv[1] = 1;
for(register int i = 2; i <= 35000; i++) {
if(np[i] == 0) prime[++cnt] = i;
for(register int j = 1; prime[j] * i <= 35000; j++) {
np[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
scanf("%d%d", &n, &m);
for(register int i = 2; i <= 200000; i++) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
for(register int i = 1; i <= n; i++) scanf("%d", a + i);
for(register int j, i = 1; i <= n; i++) {
for(j = 1; j <= _max; j++)
while(a[i] % prime[j] == 0)
sum[i][j]++, a[i] /= prime[j];
for(; prime[j] * prime[j] <= a[i]; j++) {
if(a[i] % prime[j] == 0) {
p1[i] = prime[j];
b[++sze] = p1[i];
a[i] /= p1[i];
break;
}
}
if(a[i] != 1) p2[i] = a[i], b[++sze] = p2[i];
}
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= _max; j++) sum[i][j] += sum[i - 1][j];
sort(b + 1, b + 1 + sze);
for(register int i = 1; i <= sze; i++) buc[i] = 1;
for(register int i = 1; i <= n; i++) {
if(p1[i]) p1[i] = lower_bound(b + 1, b + 1 + sze, p1[i]) - b;
if(p2[i]) p2[i] = lower_bound(b + 1, b + 1 + sze, p2[i]) - b;
}
qsize = n / sqrt(m + 1);
for(register int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
for(register int i = 0; i < n; i++) qid[i + 1] = i / qsize;
sort(q + 1, q + 1 + m, cmp);
for(register int i = 1; i <= m; i++) {
int &tmp = ans[q[i].id], l = q[i].l, r = q[i].r;
tmp = 1;
for(register int j = 1; j <= _max; j++)
tmp = 1ll * tmp * (sum[r][j] - sum[l - 1][j] + 1) % mod;
while(nowr < r) add(++nowr);
while(nowl > l) add(--nowl);
while(nowr > r) del(nowr--);
while(nowl < l) del(nowl++);
tmp = 1ll * tmp * nowans % mod;
}
for(register int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}