题解 P5071 【[Ynoi2015]此时此刻的光辉】
诗乃
2019-10-25 21:54:21
不难发现，我们要求的是$\prod_{i=1}^{n}(a_i+1)$，其中$a_i$表示第$i$个质因子的出现次数。
考虑莫队。首先一起维护所有质因子的出现次数是肯定T飞的。
考虑根号分治。有一个性质，一个数最多只有一个大于$\sqrt{v}$的质因子。一个直接的思路是把小于$\sqrt{v}$的质数先拿出来做前缀和。佛说不行，小于$\sqrt{n}$的质数太多了。
我说，那就两个。有一个性质，一个数最多只有两个大于$^3\sqrt{v}$的质因子。一个直接的思路是把小于$^3\sqrt{v}$的质数先拿出来做前缀和，剩下的去莫队维护。
佛哭了，说这样可以AC。
具体的说，对于每一个输入的数分解质因数，将小于$^3\sqrt{v}$的质因子出现次数做前缀和，大于$^3\sqrt{v}$的数存起来在莫队时维护。莫队时，对于每一个询问先转移出大质因子的乘积，随后暴力遍历所有小于$^3\sqrt{v}$的质因子统计答案即可。
```cpp
#include <bits/stdc++.h>
//#include <unordered_map>
using namespace std;
const int SV = 32000, MAXN = 100050, siz = 317, P = 19260817, S = 320;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Qry {int l, r, id;} q[MAXN];
int cmp(Qry a, Qry b) {return a.l/siz == b.l/siz ? a.r < b.r : a.l < b.l;}
struct PV {int p, v;};
bool notp[SV+5]; int p[SV+5], cntp, pre[MAXN][S+5], inv[P+1], ima, n, m, a[MAXN], ans[MAXN], id[SV+5], cnt[MAXN << 1], tot, pos[MAXN];
vector <PV> w[MAXN]; map <int, int> mp;
void add(int x) {
int l = w[x].size();
for(int i = 0; i < l; ++i) {
int pp = w[x][i].p, v = w[x][i].v;
ima = 1ll * ima * inv[cnt[pp] % P] % P;
cnt[pp] += v;
ima = 1ll * ima * (cnt[pp]) % P;
}
}
void del(int x) {
int l = w[x].size();
for(int i = 0; i < l; ++i) {
int pp = w[x][i].p, v = w[x][i].v;
ima = 1ll * ima * inv[cnt[pp] % P] % P;
cnt[pp] -= v;
ima = 1ll * ima * (cnt[pp] % P) % P;
}
}
void init() {
for(int i = 2; i <= SV; ++i) {
if(!notp[i]) p[++cntp] = i, id[i] = cntp;
for(int j = 1; j <= cntp && 1ll*i*p[j] <= SV; ++j) {
notp[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
} inv[1] = 1;
for(int i = 2; i <= P-1; ++i) inv[i] = 1ll*(P-P/i)*inv[P%i]%P;
}
void pus(int i, int x, int k) {
if(x < p[S]) pre[i][id[x]] += k;
else {
if(!mp[x]) mp[x] = ++tot, pos[tot] = x;
w[i].push_back((PV) {mp[x], k});
}
}
void Getpre() {
for(int i = 1; i <= n; ++i) {
int x = a[i];
for(int j = 1; p[j] * p[j] <= x && j <= cntp; ++j)
if(x % p[j] == 0) {
int cc = 0;
for(; x % p[j] == 0; ++cc, x /= p[j]);
pus(i, p[j], cc);
}
if(x != 1) pus(i, x, 1);
for(int j = 1; j <= S; ++j) pre[i][j] += pre[i-1][j];
}
}
int main() {
read(n); read(m); for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1; i <= m; ++i) read(q[q[i].id = i].l), read(q[i].r);
sort(q+1, q+m+1, cmp); init(); Getpre(); ima = 1;
for(int i = 1; i <= tot; ++i) cnt[i] = 1;
for(int L = 1, R = 0, l, r, i = 1; i <= m; ++i) {
l = q[i].l; r = q[i].r;
while(R < r) add(++R); while(L > l) add(--L);
while(R > r) del(R--); while(L < l) del(L++);
ans[q[i].id] = ima;
for(int j = 1; j <= S; ++j)
ans[q[i].id] = 1ll*ans[q[i].id]*(pre[r][j]-pre[l-1][j]+1)%P;
}
for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}
```