题目链接：洛谷
这个跟上上个Ynoi题目是一样的套路，首先我们知道(n=prod p_i^{alpha_i})时(d(n)=prod (alpha_i+1))。
首先对所有数分解质因数，首先预处理(leq sqrt{max a_i})的所有质数，然后一个一个试除，时间复杂度(O(frac{nsqrt{a_i}}{log{a_i}}))，在lxl的数据下跑得飞快（大家都知道，卡常是要看数据性质的）。或者使用Pollard-rho分解也是可以的。
然后莫队，维护([l,r])的乘积的所有质因子的指数和对应的答案，用hashmap维护，注意每个数至多有10个质因子，所以时间复杂度为(O(10nsqrt{n}))还常数巨大，你人没了。
首先，我们先预处理([1,i])的乘积中前168个质数（(leq 1000)的质数）的指数，询问的时候直接查询前缀和就可以单独处理了，之后至多剩下两个质因子，对这些质因子离散化之后开桶莫队。要处理当前答案还需要预处理逆元。
时间复杂度(O(mod+frac{nsqrt{a_i}}{log a_i}+168n+2nsqrt{n}))
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 100003, M = 31630, mod = 19260817;
int n, m, blo, a[N], pri[M], tot, s[N][168], inv[mod], ans[N];
bool notp[M];
inline void init(int m){
notp[0] = notp[1] = true;
for(Rint i = 2;i <= m;i ++){
if(!notp[i]) pri[tot ++] = i;
for(Rint j = 0;j < tot && i * pri[j] <= m;j ++){
notp[i * pri[j]] = true;
if(!(i % pri[j])) break;
}
}
}
int len, val[2 * N], cnt[2 * N], fac[N][2], ql = 1, qr = 0, qans = 1;
struct Query {
int l, r, id;
inline bool operator < (const Query &o) const {
if(l / blo != o.l / blo) return l / blo < o.l / blo;
if(l / blo & 1) return r > o.r;
return r < o.r;
}
} q[N];
inline void _add(int x){
++ cnt[x];
qans = (LL) qans * inv[cnt[x]] % mod * (cnt[x] + 1) % mod;
}
inline void _del(int x){
qans = (LL) qans * inv[cnt[x] + 1] % mod * cnt[x] % mod;
-- cnt[x];
}
inline void add(int x){
for(Rint j = 0;j < 2;j ++) if(fac[x][j]) _add(fac[x][j]);
}
inline void del(int x){
for(Rint j = 0;j < 2;j ++) if(fac[x][j]) _del(fac[x][j]);
}
int main(){
scanf("%d%d", &n, &m); init(31629); blo = sqrt(n);
for(Rint i = 1;i <= n;i ++) scanf("%d", a + i);
for(Rint i = 1;i <= n;i ++){
for(Rint j = 0;j < 168;j ++){
s[i][j] = s[i - 1][j];
while(!(a[i] % pri[j])) a[i] /= pri[j], ++ s[i][j];
}
if(a[i] == 1) continue;
for(Rint j = 168;j < tot;j ++)
if(!(a[i] % pri[j])){
fac[i][0] = pri[j];
if(a[i] > pri[j]) fac[i][1] = a[i] / pri[j]; break;
}
if(!fac[i][0]) fac[i][0] = a[i];
for(Rint j = 0;j < 2;j ++) if(fac[i][j]) val[++ len] = fac[i][j];
}
inv[1] = 1;
for(Rint i = 2;i < mod;i ++) inv[i] = mod - (LL) mod / i * inv[mod % i] % mod;
sort(val + 1, val + len + 1);
len = unique(val + 1, val + len + 1) - val - 1;
for(Rint i = 1;i <= n;i ++)
for(Rint j = 0;j < 2;j ++)//{
if(fac[i][j]) fac[i][j] = lower_bound(val + 1, val + len + 1, fac[i][j]) - val;
// printf("fac[%d][%d] = %d
", i, j, fac[i][j]);
// }
for(Rint i = 1;i <= m;i ++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
sort(q + 1, q + m + 1);
for(Rint i = 1;i <= m;i ++){
while(ql > q[i].l) add(-- ql);
while(qr < q[i].r) add(++ qr);
while(ql < q[i].l) del(ql ++);
while(qr > q[i].r) del(qr --);
// printf("ql = %d, qr = %d, qans = %d
", ql, qr, qans);
int tmp = qans;
for(Rint j = 0;j < 168;j ++)
tmp = (LL) tmp * (s[q[i].r][j] - s[q[i].l - 1][j] + 1) % mod;
ans[q[i].id] = tmp;
}
for(Rint i = 1;i <= m;i ++) printf("%d
", ans[i]);
}