题解 P6104 【[EER2]相同的数字】

· · 题解

最后那个相同的数只可能是 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;
}