题解：CF547C Mike and Foam

Yan719 · 2025-05-07 15:52:22 · 题解

CF547C

题意

给定一个长度为 n 的序列 a，有 q 次操作，每次操作给定一个整数 x，如果 x 已经被取出，就放回 x，否则取出 x。

每次操作后输出取出的数字中满足 i < j 且 \gcd(a_i, a_j) = 1 的二元组 (i, j) 的数量。

思路

假设当前需要取出 x，那么只需考虑取出 x 对答案的贡献。

设之前已被取出的数共 k 个，分别为 b_1, b_2, \dots, b_k。

那么 x 的贡献就是 \sum \limits _{i = 1} ^ k [\gcd(a_{b_i, a_x}) = 1]

考虑对式子进行变换，有 \sum \limits _{i = 1} ^ k [\gcd(a_{b_i}, a_x) = 1] = \sum \limits _{i = 1} ^ k \sum \limits _{d \mid \gcd(a_{b_i}, a_x)} \mu(d) = \sum \limits _{d \mid a_x} \mu(d) \cdot \sum \limits _{i = 1} ^ k [d \mid a_{b_i}]

对于 \mu(d)，由定义可知，当 d = \prod \limits _{i = 1} ^ m p_i 或 d = 1 时，\mu(d) \ne 0。

所以可以考虑只枚举满足 \mu(d) \ne 0 的因子 d。

因此，将 a_x 质因数分解，设 a_x = \prod \limits _{i = 1} ^ m p_i ^ {c_i}。

由于 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 > 5 \times 10 ^ 5，所以 m \le 7。

之后直接枚举这 m 个质因子中选择哪几个 p_i 组成 d 即可，共有 2 ^ m \le 128 种。

对于枚举的每一个 d，还需知道所有的 a_{b_i} \ (1 \le i \le k) 中有多少为 d 的倍数。

由于 d 中的每个质因子的次数都为 1，所以如果 a_{b_i} 为 d 的倍数，那么当 b_i 被取出时，在枚举 b_i 的满足 \mu(d') \ne 0 的因子 d' 时必定会枚举到 d，可以在枚举时直接统计数量。

放回 x 同理。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 5e5 + 10;

int n, q, a[N], c[M], ct;
long long cnt;
bool f[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int x; cin >> x;
        int tmp = a[x];
        vector<int> pr;
        for (int i = 2; i * i <= tmp; i++) {
            bool flag = 0;
            while (tmp % i == 0) flag = 1, tmp /= i;
            if (flag) pr.push_back(i);
        }
        if (tmp != 1) pr.push_back(tmp);

        if (!f[x]) {
            cnt += ct, ct++;
            for (int i = 1; i < (1 << pr.size()); i++) {
                int val = 1, k = 1;
                for (int j = 0; j < pr.size(); j++) {
                    if (i & (1 << j)) val *= -1, k *= pr[j];
                }
                cnt += val * c[k], c[k]++;
            }
        } else {
            ct--, cnt -= ct;
            for (int i = 1; i < (1 << pr.size()); i++) {
                int val = 1, k = 1;
                for (int j = 0; j < pr.size(); j++) {
                    if (i & (1 << j)) val *= -1, k *= pr[j];
                }
                c[k]--, cnt -= val * c[k];
            }
        }
        cout << cnt << '\n';
        f[x] ^= 1;
    }
    return 0;
}