题解：P9060 [Ynoi2002] Goedel Machine

解析：

既然是乘法，对每个质数的次幂单独考虑。

尝试用莫队去维护质数的次幂。我们现在要知道

p^{2^i-1}

的值，这个可以用倍增弄出来。

但是转移的时候需要枚举所有质因数的次幂，但是复杂度一定超了，过不了。

有关因数的问题，考虑根号分治。把所有质数次幂按照质数大小分成

\le 320

和

>320

来考虑。对于的质数的次幂之和不超过

120

，所以拿出去用前缀和处理就行了。每个数只有一个大于等于的质数，在莫队的时候

O(1)

维护就可以了。

切记：不要开 long long ，否则会时间超限。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, P = 998244353, iv = P + 1 >> 1;
int n, id[N], sq, l[N], r[N], p = 1, q, pr[N], ps[N], ret = 1, k, pp[N], cn[N], a[N], to[N], m, ans[N], c[N], fr[N], s[N];
vector<int>g[N], h[N];
int read() {
	int s = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = s * 10 + ch - 48, ch = getchar();
	return s;
}
int cmp(int x, int y) {
	if (l[x] / sq ^ l[y] / sq)
		return l[x] < l[y];
	return r[x] < r[y];
}
int pown(int x, int y) {
	if (!y)
		return 1;
	int t = pown(x, y >> 1);
	if (y & 1)
		return 1LL * t * t % P * x % P;
	return 1LL * t * t % P;
}
void add(int x, int y) {
	ret = 1LL * ret * h[x][c[x]] % P;
	c[x] += y;
	ret = 1LL * ret * g[x][c[x]] % P;
}
signed main() {
	n = read(), m = read();
	sq = sqrt(n);
	for (int i = 2; i <= 320; i++) {
		if (pr[i])
			continue;
		for (int j = i; j <= 100000; j *= i)
			ps[++k] = j, fr[k] = i;
		for (int j = 2; j * i <= 100000; j++)
			pr[i * j] = 1;
	}
	for (int i = 1; i <= 100000; i++)
		to[i] = 1;
	for (int i = 321; i <= 100000; i++) {
		if (!pr[i]) {
			g[i].push_back(i);
			h[i].push_back(pown(i, P - 2));
			for (int j = 1; j * i <= 100000; j++)
				to[i * j] = i, pr[i * j] = 1;
		}
	}
	g[1].push_back(1);
	h[1].push_back(1);
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		g[to[a[i]]].push_back(1LL * g[to[a[i]]].back()*g[to[a[i]]].back() % P);
		h[to[a[i]]].push_back(1LL * h[to[a[i]]].back()*h[to[a[i]]].back() % P);
	}
	for (int i = 1; i <= m; i++)
		l[i] = read(), r[i] = read(), id[i] = i, ans[i] = 1;
	for (int i = 1; i <= k; i++) {
		for (int j = pp[0] = 1; j <= n; j++)
			s[j] = a[j] % ps[i] == 0;
		int iv = pown(pp[0] = fr[i], P - 2);
		for (int j = 1; j <= n; j++)
			s[j] += s[j - 1], pp[j] = 1LL * pp[j - 1] * pp[j - 1] % P;
		for (int j = 1; j <= m; j++)
			ans[j] = 1LL * ans[j] * pp[s[r[j]] - s[l[j] - 1]] % P * iv % P;
	}
	sort(id + 1, id + m + 1, cmp);
	for (int i = 1; i <= m; i++) {
		while (p > l[id[i]])
			add(to[a[--p]], 1);
		while (q < r[id[i]])
			add(to[a[++q]], 1);
		while (p < l[id[i]])
			add(to[a[p++]], -1);
		while (q > r[id[i]])
			add(to[a[q--]], -1);
		ans[id[i]] = 1LL * ans[id[i]] * ret % P;
	}
	for (int i = 1; i <= m; i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

完结撒花，谢谢

题解：P9060 [Ynoi2002] Goedel Machine

文章操作

解析：

代码：

相关推荐

评论

题解：P9060 [Ynoi2002] Goedel Machine