题解 P6104 【[EER2]相同的数字】
xht
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)$。
```cpp
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;
}
```