专栏文章

题解：CF547C Mike and Foam

YYan719
CF547C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipdzrkd
此快照首次捕获于
2025/12/03 10:27
3 个月前
此快照最后确认于
2025/12/03 10:27
3 个月前
查看原文

CF547C

题意

给定一个长度为 nn 的序列 aa，有 qq 次操作，每次操作给定一个整数 xx，如果 xx 已经被取出，就放回 xx，否则取出 xx。
每次操作后输出取出的数字中满足 i<ji < j 且 gcd⁡(ai,aj)=1\gcd(a_i, a_j) = 1 的二元组 (i,j)(i, j) 的数量。

思路

假设当前需要取出 xx，那么只需考虑取出 xx 对答案的贡献。
设之前已被取出的数共 kk 个，分别为 b1,b2,…,bkb_1, b_2, \dots, b_k。
那么 xx 的贡献就是 ∑i=1k[gcd⁡(abi,ax)=1]\sum \limits _{i = 1} ^ k [\gcd(a_{b_i, a_x}) = 1]
考虑对式子进行变换，有 ∑i=1k[gcd⁡(abi,ax)=1]=∑i=1k∑d∣gcd⁡(abi,ax)μ(d)=∑d∣axμ(d)⋅∑i=1k[d∣abi]\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}]
对于 μ(d)\mu(d)，由定义可知，当 d=∏i=1mpid = \prod \limits _{i = 1} ^ m p_i 或 d=1d = 1 时，μ(d)≠0\mu(d) \ne 0。
所以可以考虑只枚举满足 μ(d)≠0\mu(d) \ne 0 的因子 dd。
因此，将 axa_x 质因数分解，设 ax=∏i=1mpicia_x = \prod \limits _{i = 1} ^ m p_i ^ {c_i}。
由于 2×3×5×7×11×13×17>5×1052 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 > 5 \times 10 ^ 5，所以 m≤7m \le 7。
之后直接枚举这 mm 个质因子中选择哪几个 pip_i 组成 dd 即可，共有 2m≤1282 ^ m \le 128 种。
对于枚举的每一个 dd，还需知道所有的 abi (1≤i≤k)a_{b_i} \ (1 \le i \le k) 中有多少为 dd 的倍数。
由于 dd 中的每个质因子的次数都为 11，所以如果 abia_{b_i} 为 dd 的倍数，那么当 bib_i 被取出时，在枚举 bib_i 的满足 μ(d′)≠0\mu(d') \ne 0 的因子 d′d' 时必定会枚举到 dd，可以在枚举时直接统计数量。
放回 xx 同理。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...