Codeforces 546C / 305 Div1 C：容斥原理動態維護互質對數

題目大意

有 n 種啤酒，第 i 種泡沫高度 a_i。初始架子為空，q 次操作：給出索引 x，若 x 在架上則移除，否則加入。每次操作後輸出架上兩兩互質的數對個數。n,q ≤ 2×10^5, a_i ≤ 5×10^5。

核心思路

動態維護：每次加入/移除 a[x]，只需計算當前架上有多少數與 a[x] 互質。利用容斥原理：一個數的質因子集合為 P，與其不互質的數 = 並集(被 p 整除)。預處理每個數的質因子，維護計數器 cnt[d] 表示架上是 d 的倍數的數的個數。查詢互質數 = 總數 - 不互質數（容斥）。修改時更新所有約數的計數。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXA = 500000;
vector primeFactors[MAXA + 5];
bool inShelf[MAXA + 5];
int cnt[MAXA + 5];
int a[200005];

void init() {
    for (int i = 2; i <= MAXA; i++) {
        if (primeFactors[i].empty()) { // i 是質數
            for (int j = i; j <= MAXA; j += i)
                primeFactors[j].push_back(i);
        }
    }
}

int query(int x) { // 返回與 x 不互質的數的個數
    const auto& pf = primeFactors[x];
    int sz = pf.size(), res = 0;
    for (int mask = 1; mask < (1 << sz); mask++) {
        int mult = 1, bits = 0;
        for (int i = 0; i < sz; i++)
            if (mask >> i & 1) { mult *= pf[i]; bits++; }
        if (bits & 1) res += cnt[mult];
        else res -= cnt[mult];
    }
    return res;
}

void modify(int x, int delta) {
    const auto& pf = primeFactors[x];
    int sz = pf.size();
    for (int mask = 1; mask < (1 << sz); mask++) {
        int mult = 1;
        for (int i = 0; i < sz; i++)
            if (mask >> i & 1) mult *= pf[i];
        cnt[mult] += delta;
    }
}

int main() {
    init();
    int n, q; scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    long long ans = 0, total = 0;
    while (q--) {
        int x; scanf("%d", &x);
        if (!inShelf[x]) {
            inShelf[x] = true;
            ans += total - query(a[x]); // 互質數 = 總數 - 不互質數
            modify(a[x], 1);
            total++;
        } else {
            inShelf[x] = false;
            modify(a[x], -1);
            total--;
            ans -= total - query(a[x]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}