2s512M。
解：先分解质因数。考虑按照质因数大小是否大于√分类。
大于的就是一个数颜色个数，莫队即可n√m。
小于的直接枚举质因数做前缀和然后O(1)查询。总时间复杂度n(√m + σ(√V))。
发现我们T飞了，发现莫队的复杂度较优，而处理小于√V的质因数较劣。我们平衡一下。
把界调整到1000。这样比lm大的至多两个，莫队常数*2。而后半部分的复杂度就变成了nσ(√V)，可以通过本题。
#include <bits/stdc++.h>
const int N = , MO = ;
inline char gc() {
static char *p1, *p2, s[N];
if(p1 == p2) p2 = (p1 = s) + fread(s, , N, stdin);
return (p1 == p2) ? EOF : *p1++;
}
template <class T> inline void read(T &x) {
x = ;
register char c(gc());
while(c < '' || c > '') {
c = gc();
}
while(c >= '' && c <= '') {
x = x * + c - ;
c = gc();
}
return;
}
int ex[N], p[N], a[N], lc[N], rc[N], fr[N], top, X[N * ], xx, inv[N], bin[N], Ans, ans[N], sum[N], exx[N];
bool vis[N];
std::vector<int> v[N], v2[N];
struct Node {
int l, r, id;
inline bool operator < (const Node &w) const {
if(fr[l] != fr[w.l]) return l < w.l;
return r < w.r;
}
}node[N];
inline void getp(int n) {
for(register int i = ; i <= n; i++) {
if(!vis[i]) p[++top] = i;
for(int j = ; j <= top && i * p[j] <= n; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) break;
}
}
return;
}
inline void add(int y) {
if(ex[y]) {
int x(ex[y]);
if(bin[x]) {
Ans = 1ll * Ans * inv[bin[x] + ] % MO;
}
++bin[x];
Ans = 1ll * Ans * (bin[x] + ) % MO;
}
if(exx[y]) {
int x(exx[y]);
if(bin[x]) {
Ans = 1ll * Ans * inv[bin[x] + ] % MO;
}
++bin[x];
Ans = 1ll * Ans * (bin[x] + ) % MO;
}
return;
}
inline void del(int y) {
if(ex[y]) {
int x(ex[y]);
Ans = 1ll * Ans * inv[bin[x] + ] % MO;
--bin[x];
if(bin[x]) {
Ans = 1ll * Ans * (bin[x] + ) % MO;
}
}
if(exx[y]) {
int x(exx[y]);
Ans = 1ll * Ans * inv[bin[x] + ] % MO;
--bin[x];
if(bin[x]) {
Ans = 1ll * Ans * (bin[x] + ) % MO;
}
}
return;
}
inline void solve(int x) {
printf("div : %d \n", x);
for(int i = ; i <= top; i++) {
if(x % p[i]) continue;
while(x % p[i] == ) {
printf("%d ", p[i]);
x /= p[i];
}
}
if(x > ) printf("%d ", x);
puts("");
return;
}
int main() {
getp();
register int n, m, lm();
//scanf("%d%d", &n, &m);
read(n), read(m);
int T = n / sqrt(m);
for(register int i(); i <= n; ++i) {
//scanf("%d", &a[i]);
read(a[i]);
fr[i] = (i - ) / T + ;
register int x(a[i]), j();
for(; p[j] <= lm && p[j] <= x; ++j) {
register int cnt();
while(x % p[j] == ) {
x /= p[j];
++cnt;
}
if(cnt) {
v[j].push_back(i);
v2[j].push_back(cnt);
}
}
if(x == ) continue;
for(; j <= top; j++) {
if(x % p[j] == ) {
exx[i] = p[j];
X[++xx] = p[j];
x /= p[j];
break;
}
}
if(x > ) {
ex[i] = x;
X[++xx] = x;
}
}
std::sort(X + , X + xx + );
xx = std::unique(X + , X + xx + ) - X - ;
for(register int i(); i <= n; ++i) {
//printf("i = %d : %d %d \n", i, ex[i], exx[i]);
if(ex[i]) {
ex[i] = std::lower_bound(X + , X + xx + , ex[i]) - X;
}
if(exx[i]) {
exx[i] = std::lower_bound(X + , X + xx + , exx[i]) - X;
}
}
for(register int i(); i <= m; ++i) {
//scanf("%d%d", &node[i].l, &node[i].r);
read(node[i].l); read(node[i].r);
node[i].id = i;
}
inv[] = inv[] = ;
for(register int i(); i <= n + ; ++i) {
inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;
}
for(register int i(); i <= fr[n]; ++i) {
lc[i] = rc[i - ] + ;
rc[i] = lc[i] + T - ;
if(i == fr[n]) rc[i] = n;
}
std::sort(node + , node + m + );
Ans = ;
add();
int l = , r = ;
for(register int i = ; i <= m; i++) {
while(r < node[i].r) {
add(++r);
}
while(node[i].l < l) {
add(--l);
}
while(node[i].r < r) {
del(r--);
}
while(l < node[i].l) {
del(l++);
}
ans[node[i].id] = Ans;
//printf("ans %d = %d \n", node[i].id, Ans);
}
/// step 2
for(register int i(); p[i] <= lm; ++i) {
int LEN(v[i].size()), p();
for(register int j(); j <= n; ++j) {
sum[j] = sum[j - ];
if(p < LEN && v[i][p] == j) {
sum[j] += v2[i][p++];
}
}
for(register int j(); j <= m; ++j) {
int x = sum[node[j].r] - sum[node[j].l - ];
ans[node[j].id] = 1ll * ans[node[j].id] * (x + ) % MO;
}
}
for(register int i(); i <= m; ++i) {
printf("%d\n", ans[i]);
}
return ;
}AC代码