题解 【P5071 [Ynoi2015] 此时此刻的光辉】

第十道Ynoi必须祭.jpg

首先这道题一眼莫队，对每个数分解质因数，然后离散化质因数，莫队开桶统计。

设 $v$ 为值域，则复杂度为 $O(n\sqrt{n}\log n+n\sqrt{v})$，跑得飞快

考虑另一种暴力的做法，前缀和统计，记 $sum[i][j]$ 为第 $[1,i]$ 的数中质因数 $j$ 出现的次数，那么每个询问可以暴力前缀和。

但 $1\sim 10^9$ 中的因数有亿点多，然而因数越大，也就意味着它在质因数一个数的质因数分解式里面出现次数越少……

自然想到根号分治。设一个阈值 $k$，则 $\le k$ 的因数前缀和统计，$>k$ 的莫队。

$k$ 取到 $\sqrt{v}$ 直接空间爆炸，所以取到 $\sqrt[3]v=1000$ 是较为优秀的方案，每个数除去所有小于等于 $1000$ 的质因子后，只会剩下至多两个质因子，所以我们就去掉了一个 $\log$，复杂度 $O(nk+mk+n\sqrt{v}+n\sqrt{m})$，即 $O(n\sqrt{v}+n\sqrt{m}+m\sqrt{v})$。

这里莫队的时候涉及除法，所以要先预处理出逆元。

代码非常好写，可以在时限的一半内通过，不知道为什么其它题解都用了PR（

其实是我不会PR

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#define int unsigned int

const int K = 1000;
const int mod = 19260817;
int a[100005], p[100005], ans[100005], cnt[500005], len, S, id, now = 1;
int fac[100005][3], sum[100005][170], R[100005][12];
int inv[200005];
bool mark[40005];
std::map<int, int> mp;
struct Quest {
	int l, r, id;
	inline bool operator < (const Quest a) {
		return (l - 1) / S == (a.l - 1) / S ? ((l - 1) / S & 1 ? r < a.r : r > a.r) : l < a.l;
	}
} q[100005];

int qpow(int a, int b) {
	int ret = 1LL;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
inline void add(int x) {
	if (fac[x][1]) {
		now = 1LL * now * inv[cnt[fac[x][1]] + 1] % mod;
		cnt[fac[x][1]] += R[x][1];
		now = 1LL * now * (cnt[fac[x][1]] + 1) % mod;
	}
	if (fac[x][2]) {
		now = 1LL * now * inv[cnt[fac[x][2]] + 1] % mod;
		cnt[fac[x][2]] += R[x][2];
		now = 1LL * now * (cnt[fac[x][2]] + 1) % mod;	
	}
}
inline void del(int x) {
	if (fac[x][1]) {
		now = 1LL * now * inv[cnt[fac[x][1]] + 1] % mod;
		cnt[fac[x][1]] -= R[x][1];
		now = 1LL * now * (cnt[fac[x][1]] + 1) % mod;
	}
	if (fac[x][2]) {
		now = 1LL * now * inv[cnt[fac[x][2]] + 1] % mod;
		cnt[fac[x][2]] -= R[x][2];
		now = 1LL * now * (cnt[fac[x][2]] + 1) % mod;
	}
}

signed main() {
	int n, m, l = 1, r = 0;
	scanf("%u%u", &n, &m);
	S = n / sqrt(m);
	inv[1] = 1;
	for (int i = 2; i <= 2 * n; ++ i)
		inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 1; i <= n; ++ i) scanf("%u", a + i);
	for (int i = 2; i <= 40000; ++ i) if (!mark[i]) {
		p[++ len] = i;
		for (int j = i * i; j <= 40000; j += i) mark[j] = true;
	}
	for (int i = 1; i <= n; ++ i) {
		int t = 0;
		for (int j = 1; j <= 168; ++ j) sum[i][j] = sum[i - 1][j];
		for (int j = 1; j <= len && p[j] * p[j] <= a[i]; ++ j)
			if (a[i] % p[j] == 0) {
				int r = 0;
				while (a[i] % p[j] == 0) a[i] /= p[j], ++ r;
				if (p[j] <= K) sum[i][j] += r;
				else fac[i][++ t] = p[j], R[i][t] = r;
			}
		if (a[i] != 1) {
			if (a[i] <= K) ++ sum[i][std::lower_bound(p + 1, p + len + 1, a[i]) - p];
			else fac[i][++ t] = a[i], R[i][t] = 1;
		}
	}
	for (int i = 1; i <= m; ++ i) {
		scanf("%u%u", &q[i].l, &q[i].r), q[i].id = i;
		int tmp = 1, l = q[i].l, r = q[i].r;
		for (int j = 1; j <= 168; ++ j)
			tmp = 1LL * tmp * (sum[r][j] - sum[l - 1][j] + 1) % mod;
		ans[i] = tmp;
	}
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= 2 && fac[i][j]; ++ j)
		if (mp.count(fac[i][j])) fac[i][j] = mp[fac[i][j]];
		else fac[i][j] = mp[fac[i][j]] = ++ id;
	std::sort(q + 1, q + m + 1);
	for (int i = 1; i <= m; ++ i) {
		while (l > q[i].l) add(-- l);
		while (r < q[i].r) add(++ r);
		while (l < q[i].l) del(l ++);
		while (r > q[i].r) del(r --);
		ans[q[i].id] = 1LL * ans[q[i].id] * now % mod;
	}
	for (int i = 1; i <= m; ++ i) printf("%u\n", ans[i]);
}