自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:17:27，当前版本为作者最后更新于2020-02-18 14:18:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最后那个相同的数只可能是 $m = \max_{i=1}^{n} a_i$ 或者 $\ge m$ 的最小质数，每次算两种的答案然后取 $\min$ 即可。

算答案的时候，将每个数加到目标值的过程按照质数划分成若干段，可以差分实现。对于长度为 $k$ 的一段，选择用 $c_1$ 还是 $c_2$ 取决于 $kc_1$ 和 $c_2$ 哪个大，显然这玩意儿是单调的，那么前缀和一下即可。

注意如果目标值是 $m$ 且 $m$ 不为质数，每个数加到 $m$ 的最后一段可能只能使用 $c_1$。

总时间复杂度 $\mathcal O(n + m + q)$。

const int N = 1e5 + 7, M = 1 << 17 | 1, P = 1e7 + 20;
int n, m, q, o, a[N], v[P], f[P], c1, c2;
vi p;
vector<ll> c[2], e[2];
ll g[2], ans;

inline void add(int o, int x, int k) {
	if (!x) return;
	if ((int)c[o].size() < x + 1) c[o].resize(x + 1);
	c[o][x] += k;
}

inline void prework(int o, int m) {
	vi d(p.size());
	for (int i = 1; i <= n; i++) {
		int x = a[i];
		if (v[x] == v[m]) add(o, m - x, 1);
		else {
			add(o, v[x] - x, 1);
			if (m == v[m]) add(o, m - p[f[v[m]]-1], 1);
			else g[o] += m - p[f[v[m]]-1];
			++d[f[v[x]]];
		}
	}
	for (ui i = 0; p[i+1] < v[m]; i++) {
		if (i) d[i] += d[i-1];
		add(o, p[i+1] - p[i], d[i]);
	}
	e[o].resize(c[o].size());
	for (ui i = 0; i < c[o].size(); i++) {
		e[o][i] = c[o][i] * i;
		if (i) e[o][i] += e[o][i-1], c[o][i] += c[o][i-1];
	}
}

inline ll solve(int o) {
	int k = min((int)1.0 * c2 / c1, (int)c[o].size() - 1);
	return (e[o][k] + g[o]) * c1 + (c[o].back() - c[o][k]) * c2;
}

int main() {
	for (int i = 2; i < P; i++) {
		if (!v[i]) p.pb(v[i] = i), f[i] = p.size() - 1;
		for (ui j = 0; j < p.size() && i * p[j] < P && p[j] <= v[i]; j++)
			v[i*p[j]] = p[j];
	}
	for (int i = P - 1; i; i--) if (v[i] != i) v[i] = v[i+1];
	rd(n), rd(q), rd(o);
	for (int i = 1; i <= n; i++) rd(a[i]), m = max(m, a[i]);
	prework(0, m), prework(1, v[m]);
	for (int i = 1; i <= q; i++) {
		rd(c1), rd(c2), c1 ^= o * ans, c2 ^= o * ans;
		print(ans = min(solve(0), solve(1)));
		ans &= M - 2;
	}
	return 0;
}